西安电子科技大学数据结构期末复习题.doc

《西安电子科技大学数据结构期末复习题.doc》由会员分享，可在线阅读，更多相关《西安电子科技大学数据结构期末复习题.doc（9页珍藏版）》请在装配图网上搜索。

www.juanjuantx.com 所有试卷资料免费下载 西安电子科技大学 《数据结构》复习题 （含部分参考答案版） 一、 单项选择题 1. 按照数据逻辑结构的不同，可以将数据结构分成 C 。 A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 线性结构和非线性结构 D. 内部结构和外部结构 2. 下列关于数据结构的叙述中正确的是 A 。 A. 数组是同类型值的集合 B. 递归算法的程序结构比迭代算法的程序结构更为复杂 C. 树是一种线性的数据结构 D. 用一维数组存储二叉树，总是以先序顺序遍历各结点 3. 在计算机的存储器中表示时，物理地址与逻辑地址相同并且是连续的，称之为 B A.逻辑结构 B.顺序存储结构 C.链式存储结构 D.以上都不对 4. 以下关于算法特性的描述中， B 是正确的。 （1）算法至少有一个输入和一个输出 （2）算法至少有一个输出但是可以没有输入 （3）算法可以永远运行下去 A. （1） B. （2） C. （3） D. （2）和（3） 5. 对顺序存储的线性表（a1,a2,…,an）进行插入操作的时间复杂度是 C 。 A.O(n) B. O(n-i) C. (n/2) D. O(n-1) 6. 链表不具有的特点是 A 。 A.可随机访问任一元素 B.插入和删除时不需要移动元素 C.不必事先估计存储空间 D.所需空间与线性表的长度成正比 7.线性链表中各链结点之间的地址 C 。 A.必须连续 B.部分地址必须连续 C.不一定连续 D.连续与否无关 8. 以下关于链式存储结构的叙述中， C 是不正确的。 A.结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构 B.逻辑上相邻的结点物理上不必邻接 C.可以通过计算直接确定第i个结点的存储地址 D.插入、删除操作方便，不必移动结点 9. 设依次进入一个栈的元素序列为d, a, c, b,得不到出栈的元素序列为 D 。 A. dcba B. acdb C. abcd D. cbda 10. 将新元素插入到链式队列中时，新元素只能插入到 B 。 A. 链头 B. 链尾 C. 链中 D. 第i个位置，i大于等于1，大于等于表长加1 11. 设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、和e1，则栈S容量至少应该是 C 。 A. 6 B. 4 C. 3 D. 2 12.下面 D 是‘abcd321ABCD’的子串。 A. abcd B. 321ab C. ‘abc ABC’ D. ‘21AB’ 13.假设8行10列的二维数组A[1…8，1…10]分别以行序为主序和以列序为主序顺序存储时，其首地址相同，那么以行序为主序时元素a[3，5]的地址与以列序为主序时 C 元素相同。 A. a[7，3] B. a[8，3] C. a[1，4] D. ABC都不对 14. 数组A[0…5，0…6]的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址为 A 。 A. 1175 B. 1180 C. 1205 D.1210 15.下列广义表中，长度为3的广义表为 B 。 A.（a,b,c,( )） B. ((g),(a,b,c,d,f),( )) C. (a,(b,(d))) D. ((( ))) 16. 以下关于广义表的叙述中，正确的是 A 。 A. 广义表是0个或多个单元素或子表组成的有限序列 B. 广义表至少有一个元素是子表 C. 广义表不可以是自身的子表 D. 广义表不能为空表 17.若树T有a个度为1的结点，b个度为2的结点，c个度为3的结点，则该树有 D 个叶结点。 A. 1+2b+3c B. a+2b+3c C.2b+3c D. 1+b+2c 18.若一棵二叉树有102片叶子结点，则度二叉树度为2的结点数是 B 。 A. 100 B. 101 C. 102 D. 103 19. 在有n 个叶子结点的霍夫曼树中，其结点总数为： 。 A. n B. 2n C. 2n +1 D. 2n - 1 20.具有12个结点的完全二叉树有 B 。 A. 5个叶子结点 B. 5个度为2的结点 C. 7个分支结点 D. 2个度为1的结点 21.设结点x和y是二叉树中的任意两结点，若在先根序列中x在y之前，而后根序列中x在y之后，则x和y的关系是 C 。 A. x是y的左兄弟 B. x是y的右兄弟 C. x是y的祖先 D. x是y的后代 22. 先序遍历序列与中序遍历序列相同的二叉树为 。 A. 根结点无左子树的二叉树 B.根结点无右子树的二叉树 C. 只有根结点的二叉树或非叶子结点只有左子树的二叉树 D. 只有根结点的二叉树或非叶子结点只有右子树的二叉树 23.若二叉树T的前序遍历序列和中序遍历序列分别是bdcaef和cdeabf，则其后序遍历序列为 A 。 A. ceadfb B. feacdb C. eacdfb D. 以上都不对 24.设无向图的顶点个数为n，则该图最多有 C 条边。 A. n-1 B. n(n-1) C. n(n-1)/2 D. n 25.对于一个有n个顶点和e条边的无向图，若采用邻接表表示，邻接表中的结点总数是 C 。 A. e/2 B. e C. n+2e D. n+e 26. 无向图G=（V，E），其中V=｛a,b,c,d,e,f｝,E=｛(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)｝。 对该图进行深度优先遍历，下面不能得到的序列是 D 。 A. acfdeb B. aebdfc C. aedfcb D. abecdf 27.在下述排序方法中，不属于内排序方法的是 C 。 A. 插入排序法 B. 选择排序法 C. 拓扑排序法 D. 归并排序法 28. 直接插入排序在最好情况下的时间复杂度为 B 。 A. O(log2n) B. O(n) C. O(nlog2n) D. O(n2) 29.对有n个记录的表作快速排序，在最坏情况，算法的时间复杂度是 D 。 A. O(n3) B. O(n) C. O(nlog2n) D. O(n2) 30.下面的排序算法中，稳定是 A 。 A. 直接插入排序法 B. 快速排序法 C. 直接选择排序法 D. 堆排序法 二、 填空题 1. 一个算法具有5个特性： 、 、 、有零个或多个输入，一个或多个输出。 2. .设数组a[1…50，1…80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45，68]的存储地址为 9174 ；若以列序为主序顺序存储，则元素a[45，68]的存储地址为 8788 。 3. 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用 存储结构。 4.两个字符串相等的充分必要条件是 长度相等且对应位置上的字符相等 。 5. 字符串“abcd”中共有 个长度大于0的字串。 6. 广义表list=（5，（3，2，（14，9，3），（），4），2，（6，3，10））的长度及深度分别 为 和 。 7.若二叉树的先序序列和后序序列相反，则该二叉树一定满足只有一个叶子结点 。 8.若无向图满足 有n-1条边的连通图 ，则该图是树。 9.若无向图中有n个顶点，则其边数最少为 n-1 ，最多为 n(n-1)/2 。 10.堆排序的时间复杂度和空间复杂度分别为 O(nlog2n) 和 O(1) 。 三、 名词解释 （1）抽象数据类型 （2）算法及其特性 （3）串的模式匹配 （4）优先级队列 （5）完全二叉树 （6）堆（7）Huffman编码（8）Huffman树 （9）连通分量及重连通分量（10）最小生成树（11）克鲁斯卡尔算法 （12）普里姆算法（13）希尔排序（14）快速排序 （15）教材等等相关名次解释题 四、 简答题 1. 请对线性表进行顺序存储和链式存储的特点作比较。（西电2004年考研试题） 2. 单链表为什么要引入头结点？ 3.线性表的链式存储结构有单链表、循环链表、双向链表，试问它们各有什么优点和缺点？ 参考答案： l 单链表的优点是空间动态分配，插入和删除时不需要移动数据，缺点是不能随机访问数据。和其它两种相比，它还节省了空间。 l 循环链表除了具有单链表的优点外，它从任意结点出发可以找到其它结点。缺点同单链表的缺点。 l 双向链表除了具有循环链表的优点，它还可以方便地找到某个结点的前驱。缺点是增加了空间开销。 4.内存中一片连续空间（不妨假设地址从1到m），提供给两个栈使用，怎样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。 5. 假设有一个适当大小的栈S，输入栈的序列为A，B，C，D，E。 问：（1）能否得到下列的输出序列： ① B，C，D，E，A； ② E，A，B，C，D； ③E，D，C，B，A。 （2）写出所有可能正确的输出序列（至少5种）。 6.用向量表示的循环队列的队首和队尾位置分别为1和max_size，试给出判断队列为空和为满的边界条件。 l 参考答案： 队空条件为max_size==1; 队满的条件为（max_size+1）%MAXSIZE. 7. 设一棵二叉树后序遍历序列为DGJHEBIFCA，中序遍历序列为DBGEHJACIF，要求： （1）画出该二叉树； （2）写出该二叉树的先序遍历序列； （3）画出该二叉树对应的森林。 8.对二叉树中的结点按层次顺序（每一层自左向右）进行的访问操作称为二叉树的层次遍历。现已知一棵二叉树的层次序列为AEBGFDIMH，中序遍历序列为GEFAMDBHI。请画出该二叉树并写出其先序序列。若将该二叉树看作是一个森林的孩子 — 兄弟表示，请画出该森林。（西电2004年考研试题） 9. 已知某通信电文仅由A、B、C、D、E、F这6个字符构成，其出现的频率分别为23、5、14、8、25、7，请给出它们的霍夫曼树及其对应的霍夫曼编码。 10.给定下列图G用两种不同表示法画出该图的存储结构图。 A B G F E D C 4 8 122 4 20 12 15 10 11. 针对上图分别用卡鲁斯卡尔及普里姆算法给出该图的最小生成树，画出其逻辑结构。 12.总结直接插入排序、折半插入排序、希尔排序、起泡排序、快速排序、简单选择排序、锦标赛排序、堆排序及归并排序等在最好情况下、最坏情况及平均的时间复杂度，辅助空间复杂度及稳定性。 13.判断下面的每个结点序列是否表示一个堆，如果不是堆，请把它调整为堆。 （1）100，90，80，60，85，75，20，25，10，70，65，50 （2）100，70，50，20，90，75，60，25，10，85，65，80 14.已知一序列（12，70，33，65，24，56，48，92，86，33），问该序列是否是堆？如果不是，则把它调整为小顶堆。并问把该序列调整为堆共需要多少次元素间的比较？多少次元素间的交换。（西电2005年考研试题） 15.试为下列情况选择合适的排序算法：（西电2006年考研试题） （1）n=30，且要求最坏情况下速度最快； （2）n=30，且要求既要快，又要排序稳定； （3）n=2000，要求平均情况下速度最快； （4）n=2000，要求最坏情况下速度最快，又要节省存储空间。 五、 算法设计题 1. 实现一个算法，完成在不带表头结点的单链表第i个结点之前插入新元素x的操作。 （教材P74页） 2.（a）实现一个函数，完成在带表头结点的双向循环链表中，建立一个包含有值value的新结点并将其插入到当前结点之后。（教材P91页） （b）实现一个函数，完成在带表头结点的双向循环链表中删除当前结点，同时让当前指针指到链表中下一个结点位置。（教材P91页） 3.（a）实现一个函数完成删除链式栈顶结点，返回被删栈顶元素的值。（教材P107页） （b）实现一个函数完成删除链式队列队头结点，并返回被删对头元素的值。（教材P117页） 4.对二叉链表，实现一个函数Parent(*BinTreeNode*start, *BinTreeNode*curent)从结点start开始，搜索结点current的双亲结点，并返回其地址，否则返回NULL。（教材P171页） 5. 若用二叉链表作为二叉树的存储表示，试针对下列问题编写递归算法： （1）统计二叉树中叶子结点的个数； （2）交换每个结点的左子女和右子女。 6.熟练掌握直接插入排序、折半插入排序、希尔排序、起泡排序、快速排序等其它排序的算法 7.若以域变量rear和length分别指示循环队列中队尾元素的位置和队列中元素的个数。请完成下面的入队列和出队列的算法：（西电2004年考研试题） #define MAXQSIZE 100 //最大队列长度 Type struct｛ Qelemtype *base; //base为队列所在区域的首地址 int length; //队列长度 int rear; //队尾元素位置 ｝SqQueue; Status EnQueue(SqQueue &Q, Qelemtype e) ｛ if ( ① ) return ERROR; // 队列满，无法插入 Q.rear= ② ; //计算元素e的插入位置 ③ = e; //在队尾加入新的元素 Q.length++; //队列长度加1 return OK; ｝ Status DeQueue(SqQueue &Q, Qelemtype &e) //删除对头元素，并用e带回其值 ｛ if ( ④ )return ERROR; //队列满 e=Q.base[ ⑤ ]; //取队头元素 Q．length --; //队列长度减1 return OK; ｝ 8.请运用快速排序思想，设计递归算法实现求n（n＞1）个不同元素集合中的第i（1≤i≤n）小元素。（西电2004年考研试题） 9.阅读下列函数说明及相应代码，在空白处填入相应语句。 (西电2005年考研试题) [函数1] 函数palinddrome(char s[])的功能是：判断字符串s是否为回文字符串，若是，则返回0，否则返回-1。若一个字符串顺读和倒读都一样时，称该字符串是回文字符串，例如：“LEVEL”是回文字符串，而“LEVAL”不是。 Int palindrome (char s[]) {char *pi, *pj; Pi = s; pj =s + strlen(s) – 1; //*strlen(s)函数用于求得串s的串长 While（pi＜pj && ① ）{ Pi ++; pi - - ; } if ( ② )return - 1; else return 0; } [函数2] 函数insert_sort(int a[],int count)是用直接插入排序法对指定数组的前count个元素从小到大排序。 Void insert_sort(int a[], int count) { int i, j, t; for (i=1;i＜count;i++){//控制a[i]，…a[count-1]的比较和插入 t = a[i]; j= ③ ; while (j≥0&&t＜a[j]){ //在有序部分寻找元素a[i]的插入位置 ④ ; j - -; } ⑤ ; } } 10. 假设以数组seq[0…m-1]存放循环队列中的元素，同时设变量rear和quelen分别指示循环队列中的队尾元素的位置和内含元素的个数。(西电2006年考研试题) 请给出： （1）给出循环队列的队满条件和队空条件； （2）写出相应的入队列和出队列的算法，并分别分析其时间代价； （3）如果用数组sequ[m…n]来存放循环队列中的元素，则（2）中的入队列和出队列的算法中的哪些语句要修改？如何修改？ 第 9 页 共 9 页