数据结构导论复习卷-数据结构导论试题.docx

《数据结构导论复习卷-数据结构导论试题.docx》由会员分享，可在线阅读，更多相关《数据结构导论复习卷-数据结构导论试题.docx（6页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数据结构导论复习综合卷一、选择题I.关于算法的描述，不正确的选项是1 B ）A.算法最终必须由计算机程序实现B.所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界C.健壮的算法不会因非法的输入数据而出现莫名其妙的状态D.算法的优劣与算法描述语言无关.假设用个有6个单元的数组来实现循环队列，rear和front的初值分别为0和3。那么从队列中删除一个元 素、再添加两个元素后，rear和from的值分别为（B ）B.2 和 4D.5 和 IA.1 和 5C.4 和 2.数据的四种根本逻辑结构是指（DA.数组、链表、树、图形结构 B.线性表、链表、栈队列、数组广义表C.线性结构、链表、树、图形

2、结构 D.集合、线性结构、树、图形结构.数据结构中，通常采用两种方法衡量算法的时间复杂性，即（D ）。A.最大时间复杂性和最小时间复杂性B.最好时间复杂性和最坏时间复杂性C.局部时间复杂性和总体时间复杂性D.平均时间复杂性和最坏时间复杂性.以下关于线性表的表达中，不正确的选项是（C ）。A.线性表是n个结点的有穷序列B.线性表可以为空表C.线性表的每一个结点有且仅有一个前趋和一个后继D.线性表结点间的逻辑关系是1:1的联系.在一个单链表中，假设p所指结点不是最后结点，那么删除p所指结点的后继结点的正确操作是（CA. p=p-nextB. p-next =p-nextC. p-next=p-ne

3、xt-nextD. p-next=p.栈和队列（CA.共同之处在于二者都是先进先出的特殊的线性表6 .共同之处在于二者都是先进后出的特殊的线性表C.共同之处在于二者都只允许在顶端执行删除操作D.没有共同之处.一个有序表为1, 3, 9, 12, 32, 41, 45, 62, 75, 77, 82, 95, 100,当二分查找值为82的结点时，查找成功时的比拟次数为（ C ）A.1A.1B.2C.4D.8.向一个栈顶指针为hs的链栈中插入一个*s结点时，应执行的操作为（B ）A.hsnext=s；B.s-next=hs； hs=s；C.snext=hsnext； hsnexl=s；D.snex

4、t=hs； hs=hsnext；. 8个元素（34, 76, 45, 18, 26, 54, 92, 65）,按照依次插入结点的方法生成一棵二叉排序树，那么该树 的深度为（B ）A.4B.5C.6D. 7.二维数组A56采用按列为主序的存储方式，每个元素占3个存储单元，假设A0的存储地址是100, 那么A43的存储地址是（D ）。A. 127B. 142C. 15012 .深度为k的二叉树至多有(CA. 2k个结点 B. 个结点C. 15013 .深度为k的二叉树至多有(CA. 2k个结点 B. 个结点D. 157C. 2k-l个结点D. 2bLi个结点14 .对于如以下图所示二叉树采用中根遍

5、历，正确的遍历序列应为(D)。A. ABCDEFC. CDFBEAD. CBDAEF)o15 .下面关于生成树的描述中，不正确的选项是(AA.生成树是树的一种表现形式B.生成树一定是连通的C.生成树一定不含有环A. V|V2V3V4V5C. CV4 V3 V5 V2B. V|V2V3V5V4D. V1V3V4V5V216 .用于外存储器的数据组织结构散列文件，主要适用于(B )。A.顺序存取C.索引存取B.随机存取D.以上三种都可以17 .堆排序属于一种选择排序，其时间复杂性为(B )A. O (I)B. O (nlog2n)C. O (n)D. O (n2)18 .以下排序方法中，属于不稳定

6、的排序方法是(A )oA.直接选择排序法C.基数排序法B.冒泡排序法D.归并排序法19 .以下查找方法中，不属于动态的查找方法是(D )。A.二叉排序树法C.散列法B.平衡树法D.斐波那契查找法20.要解决散列引起的冲突问题，常采用的方法有(D )oA.数字分析法、平方取中法B.数字分析法、线性探测法C.二次探测法、平方取中法D.二次探测法、链地址法二、填空题1 .在一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比拟_3+1)/2 个元素结点。2 .具有n个叶子结点的哈夫曼树，其结点总数为2n-l。3 .栈的插入与删除操作在一栈顶进行。4 .一棵二叉树的广义表表示

7、为a(b(c,d),c(f(, g),那么。结点的双亲结点为_a_,左孩子结点为f, 右孩子结点为一空结点。5 .在一个具有n个顶点的无向完全图中，包含有n(n-l)/2条边，在一个具有n个顶点的有向完全图 中，包含有 n(n-l)条边。6 .表示图的三种存储结构为 邻接矩阵 _、 邻接表 和边集数组o.对n个元素进行冒泡排序时，最少的比拟次数为n-1。7 .在插入排序、冒泡排序、快速排序、归并排序等排序算法中，占用辅助空间最多的是_归并排序。8 .以二分查找方法查找一个线性表时，此线性表必须是顺序存储的有序表。9 .每次直接或通过基准元素间接比拟两个元素,假设出现逆序排列时就交换它们的位置，

8、此种排序方法叫做 快速排序；每次使两个相邻的有序表合并成一个有序表的排序方法叫做归并排序。10 .在双链表中，存储一个结点有三个域，一个是数据域，另两个是指针域，分别指向一直接前趋和直接后继o11 .快速排序在平均情况下的空间复杂度为0(log2n),在最坏情况下的空间复杂度为0(n)。三、算法完善.下面程序段为删除循环链表中第一个info域值等于x的结点，请填上程序中缺少的局部。循环链表的结构如题34图所示：题34图stinct node int info;struct node *link; int Delete (struct node *head, int x) struct node

9、 *p, *q; /*p:当前处理的结点；q： p的前驱结点*/ if (! head ) return (0);if (head- link =hcad) if (head-*info=x) free (head);head=NULL； return (x)return (0);Ip=hcad; q=hcad;while (qlink!二head) q=qT I i nk;while (p-link!=hcad) if(p-info=x) qT I ink=p- I ink；if (p=head) head=pT I ink;free (p);return (x);Ielse q=p ;p=

10、 pT I ink_;)return (0);).求出指定结点在给定的二叉排序树中所在的层次Void level (BSTree root, p) int level=0；if ( ! root)return；clscievel+；while (root-key!=pkey) if (root-keykey)level (root-rchi Id, p)else level (root- Ichi Id, p) ； levcl+：Iprint (the level i s %d : n , I eve I 3.完善以下折半插入排序算法。Void binasort (struct node r

11、MAXSIZE, int n) for (i=2； i=n； i+) r 0 =r i； low= 1 ； high=i-l ； while (lowv二high) mid= ( I ow+h i ght/2 _if (r 0 .key=low； j-) rj+1=rj： r low =r ()；四、设计题.二叉树是由所有度数不大于2的结点构成的一种特定树，假设某结点度为2,那么该结点有左右两个孩子, 请编写算法计算一二叉树所有度数为2的结点个void treedoubleCount (bitreptr t, int *count) if (t! =NULL) if ( (t - Ichild

12、 = =NULL & t - rchild = = NULL)*count + +；/*t所指的结点是度为2的结点，累加器加1*/treedoubleCount (t - Ichild, count) ； /*累计左子树上度为 2 的结点*/ treedoubleCount (t - rchild, count) ； /*累计右子树上度为 2 的结点*/ ).试编写一算法，以完成在带头结点单链表L中第i个位置前插入元素X的操作。void insert_lklist (Iklist L, int i, datatype x) P=L; j=0while ( (p-next!=NULL) & (jnext； j+;)if (i! =j)error (不存在第i个位置)； else s=malloc (size)； s-data=x； s-next =p-next； /*插入结点*/ p-next=s；)