《数据结构》3套模拟试题综合测试题带答案4.doc

《《数据结构》3套模拟试题综合测试题带答案4.doc》由会员分享，可在线阅读，更多相关《《数据结构》3套模拟试题综合测试题带答案4.doc（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构模拟试题10一、单项选择题（每题 3 分，共30分）1设某无向图有n个顶点，则该无向图的邻接表中有（ ）个表头结点。(A) 2n(B) n(C) n/2(D) n(n-1)2设无向图G中有n个顶点，则该无向图的最小生成树上有（ ）条边。(A) n(B) n-1(C) 2n(D) 2n-13设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键字45为基准而得到的一趟快速排序结果是（ ）。(A) 40，42，60，55，80，85(B) 42，45，55，60，85，80(C) 42，40，55，60，80，85(D) 42，40，60，85，55，804（ ）

2、二叉排序树可以得到一个从小到大的有序序列。(A) 先序遍历(B) 中序遍历(C) 后序遍历(D) 层次遍历5设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（ ）。(A) 2i+1(B) 2i(C) i/2(D) 2i-16程序段s=i=0；do i=i+1； s=s+i；while(inext=0(C) head-next=head(D) head!=08设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（ ）。(A) 20(B) 256(C) 512(D) 10249设一组初始记录关键字序列为(13，18，24，35，47，50，62，8

3、3，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为（ ）。(A) 1(B) 2(C) 3(D) 410.设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（ ）。(A) top=top+1;(B) top=top-1;(C) top-next=top; (D) top=top-next;二、填空题（每题2分，共20分）1. 设指针变量p指向双向链表中的结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为_=p；s-right=p-right；_=s； p-right-left=s；（设结点中的两个指针域分别为left和right）

4、。2. 设完全有向图中有n个顶点，则该完全有向图中共有_条有向条；设完全无向图中有n个顶点，则该完全无向图中共有_条无向边。3. 设关键字序列为(Kl，K2，Kn)，则用筛选法建初始堆必须从第_个元素开始进行筛选。4. 解决散列表冲突的两种方法是_和_。5. 设一棵三叉树中有50个度数为0的结点，21个度数为2的结点，则该二叉树中度数为3的结点数有_个。6. 高度为h的完全二叉树中最少有_个结点，最多有_个结点。7. 设有一组初始关键字序列为(24，35，12，27，18，26)，则第3趟直接插入排序结束后的结果的是_。8. 设有一组初始关键字序列为(24，35，12，27，18，26)，则第

5、3趟简单选择排序结束后的结果的是_。9. 设一棵二叉树的前序序列为ABC，则有_种不同的二叉树可以得到这种序列。10. 下面程序段的功能是实现一趟快速排序，请在下划线处填上正确的语句。struct record int key;datatype others;void quickpass(struct record r, int s, int t, int &i) int j=t; struct record x=rs; i=s; while(ij) while (ix.key) j=j-1; if (ij) ri=rj;i=i+1; while (_) i=i+1; if (ileft=p，

6、p-right2. n(n-1)，n(n-1)/23. n/24. 开放定址法，链地址法5. 146. 2h-1，2h-17. (12，24，35，27，18，26)8. (12，18，24，27，35，26)9. 510. ij & ri.keynext=0) return; for(q=head; q!=0;q=q-next) min=q-data; s=q; for(p=q-next; p!=0;p=p-next) if(minp-data)min=p-data; s=p; if(s!=q)t=s-data; s-data=q-data; q-data=t; 2. 设计在顺序存储结构上实

7、现求子串算法。void substring(char s , long start, long count, char t ) long i,j,length=strlen(s); if (startlength) printf(The copy position is wrong); else if (start+count-1length) printf(Too characters to be copied);else for(i=start-1,j=0; ikey=x) return; else if (bt-keyx) level(bt-lchild,x); else level(b

8、t-rchild,x);数据结构模拟试题11一、单项选择题（每题 3 分，共30分）1. 字符串的长度是指（ ）。(A) 串中不同字符的个数(B) 串中不同字母的个数(C) 串中所含字符的个数(D) 串中不同数字的个数2. 建立一个长度为n的有序单链表的时间复杂度为（ ）(A) O(n)(B) O(1)(C) O(n2)(D) O(log2n)3. 两个字符串相等的充要条件是（ ）。(A) 两个字符串的长度相等(B) 两个字符串中对应位置上的字符相等(C) 同时具备(A)和(B)两个条件(D) 以上答案都不对4. 设某散列表的长度为100，散列函数H(k)=k % P，则P通常情况下最好选择（

9、 ）。(A) 99(B) 97(C) 91(D) 935. 在二叉排序树中插入一个关键字值的平均时间复杂度为（ ）。(A) O(n)(B) O(1og2n)(C) O(nlog2n)(D) O(n2)6. 设一个顺序有序表A1:14中有14个元素，则采用二分法查找元素A4的过程中比较元素的顺序为( )。(A) A1，A2，A3，A4(B) A1，A14，A7，A4(C) A7，A3，A5，A4(D) A7，A5 ，A3，A47. 设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（ ）。(A) 8(B) 7(C) 6(D) 58. 设一棵三叉树中有2个度数为1的结点，2个度数为2的结点，2

10、个度数为3的结点，则该三叉链权中有（ ）个度数为0的结点。(A) 5(B) 6(C) 7(D) 89. 设无向图G中的边的集合E=(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（ ）。(A) aedfcb(B) acfebd(C) aebcfd(D) aedfbc10. 队列是一种（ ）的线性表。(A) 先进先出(B) 先进后出(C) 只能插入(D) 只能删除 二、填空题（每题2分，共20分）1 设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则以d=4为增量的一趟希尔排序

11、结束后的结果为_。2 下面程序段的功能是实现在二叉排序树中插入一个新结点，请在下划线处填上正确的内容。typedef struct nodeint data;struct node *lchild;struct node *rchild;bitree;void bstinsert(bitree *&t,int k)if (t=0 ) _;t-data=k;t-lchild=t-rchild=0;else if (t-datak) bstinsert(t-lchild,k);else_;3 设指针变量p指向单链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X需要执行的语句序列

12、：s-next=p-next; _;。4 设指针变量head指向双向链表中的头结点，指针变量p指向双向链表中的第一个结点，则指针变量p和指针变量head之间的关系是p=_和head=_（设结点中的两个指针域分别为llink和rlink）。5 设某棵二叉树的中序遍历序列为ABCD，后序遍历序列为BADC，则其前序遍历序列为_。6 完全二叉树中第5层上最少有_个结点，最多有_个结点。7 设有向图中不存在有向边，则其对应的邻接矩阵A中的数组元素Aij的值等于_。8 设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则第4趟直接选择排序结束后的结果为_。9 设连通图G中有n

13、个顶点e条边，则对应的最小生成树上有_条边。10 设有一组初始记录关键字序列为(50，16，23，68，94，70，73)，则将它们调整成初始堆只需把16与_相互交换即可。三、判断题（每题 2 分，共20分）1. 如果两个关键字的值不等但哈希函数值相等，则称这两个关键字为同义词。（ ）2. 设初始记录关键字基本有序，则快速排序算法的时间复杂度为O(nlog2n)。（ ）3. 分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。（ ）4. 二维数组和多维数组均不是特殊的线性结构。（ ）5. 向二叉排序树中插入一个结点需要比较的次数可能大

14、于该二叉树的高度。（ ）6. 如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。（ ）7. 非空的双向循环链表中任何结点的前驱指针均不为空。（ ）8. 不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。（ ）9. 图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问过。（ ）10. 稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。（ ）四、算法设计题（每题15分，共30分）1. 设计一个在链式存储结构上统计二叉树中结点个数的算法。2. 设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。7数据结构模拟试

15、题11参考答案一、单项选择题（每题 3 分，共30分）1C2C3C4B5B6C7B8C9A10A二、填空题（每小题2分，共20分）1. (49，13，27，50，76，38，65，97)2. t=(bitree *)malloc(sizeof(bitree)，bstinsert(t-rchild,k)3. p-next=s4. head-rlink，p-llink5. CABD6. 1，167. 08. (13，27，38，50，76，49，65，97)9. n-110. 50三、判断题（每题 2分，共20分）1对2错3对4错5错6对7对8对9对10对四、算法设计题（每题15分，共30分）1.

16、 设计一个在链式存储结构上统计二叉树中结点个数的算法。void countnode(bitree *bt,int &count) if(bt!=0) count+; countnode(bt-lchild,count); countnode(bt-rchild,count);2. 设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。typedef struct int vertexm; int edgemm;gadjmatrix;typedef struct node1int info;int adjvertex; struct node1 *nextarc;glinklistnode;typ

17、edef struct node2int vertexinfo;glinklistnode *firstarc;glinkheadnode;void adjmatrixtoadjlist(gadjmatrix g1 ,glinkheadnode g2 )int i,j; glinklistnode *p;for(i=0;i=n-1;i+) g2i.firstarc=0;for(i=0;i=n-1;i+) for(j=0;jadjvertex=j;p-nextarc=gi.firstarc; gi.firstarc=p;p=(glinklistnode *)malloc(sizeof(glink

18、listnode);p-adjvertex=i;p-nextarc=gj.firstarc; gj.firstarc=p;数据结构模拟试题12一、填空题（每小题2分，共18分）1、 数据的逻辑结构包括 ， 和 三种结构。2、 算法分析的两个主要方面是 和 。3、 在双向链表中，每个结点有两个指针域，一个指向 ，另一个指向 。4、 空串是 ，其长度等于 。5、 有一个10阶对称矩阵A，采用压缩存储方式，以行为主存储下三角形到一个一维数组中，若A00的地址是200（每个元素占2个基本存储单元），则A95的地址是 。6、 在非空二叉树的中序遍历序列中，根结点的右边 。7、 采用邻接链表存储图，则图的

19、深度优先搜索算法类似于二叉树的 。8、 在分块查找方法中，首先查找 ，然后再查找相应的 。9、 对于文件，按其记录的类型可将文件分为 文件、 文件。二、单项选择题（请将答案写在题目后的括号中。每题2分，共18分）1、有如下递归函数fact(n)，其时间复杂度是（ ）。Fact(int n) if (nLchild ; if (top=0) bool=0 ; else ; visit( p-data ) ; ; while ( ) ; 3、 折半查找算法。int Bin_Search(SSTable ST , KeyType key) int Low=1，High=ST.length, Mid

20、; while (LowHigh) ; if (ST. elemMid.key=key) return(Mid) ; else if (ST. elemMid.keykey) Low=Mid+1 ;else High=Mid-1 ; ; 4、 简单选择排序算法。void simple_selection_sort(Sqlist *L) int m, n , k;for (m=1;mlength;m+) k=m ; for (n=m+1;nlength;n+) if ( ) k=n ; if ( ) L-R0=L-Rm; L-Rm=L-Rk; ; 五、编写算法（要求给出相应的数据结构说明，14分

21、）将以L为头结点的单链表中值重复的结点删除，使所得的结果链表中所有结点的值均不相同；并对算法进行分析。19数据结构模拟试题12参考答案一、填空题（每小题2分，共18分）1、 线性结构 树形结构 图（或网）状结构2、 时间复杂度 空间复杂度3、 (直接)前驱结点 (直接)后继结点4、 零个字符组成的串 0 5、 3006、 只有右子树上的所有结点7、 先序遍历8、 索引 块9、 操作系统 数据库二、单项选择题（请将答案写在题目后的括号中。每题2分，共18分）题号123456789答案ABCBDBBCD三、分析题（每题6分，共30分）fabcehidgNULLfabcehidg图(a) 二叉树图(

22、b) 后序线索化树1、 解：所画出的二叉树如图(a)所示。树的后序遍历序列是gdhiebfca，其后序线索化树如图(b)所示。2、 解：该网的邻接链表如下图所示：0123412345293758193441351124174321333532114318从顶点V1出发的广度优先搜索的顶点序列是12354，相应的生成树如下：1524389137从顶点V1出发广度优先搜索生成树从顶点V5出发的最小生成树1524333473、 解：将关键字序列（14，9，18，7，4，13，25，19，6）依此插入到初态为空的二叉排序树中所得到的二叉排序树T如图(a)所示；删除18之后的二叉排序树T1如图(b)所示

23、；最后再插入18之后的二叉排序树T2。149197134256图(b) 删除18的二叉排序树14918713419256图(a) 生成的二叉排序树14919713418256图(c) 插入18后的二叉排序树4、 解：根据所给定的散列函数和处理冲突方法，得到的散列表结构如下：0123456789103356 25477117 298 4295 69成功查找的平均查找长度：ASL=(18+22+31)/11=17/115、 解：做非递减排序时的每一趟结果如下：初始关键字：35，29，52，60，17，9，38，27，13，45第一趟： 29，35 52，60 9，17 27，38 13，45第二趟

24、： 29，35，52，60 9，17，27，38 13，45第三趟： 29，35，52，60 9，13，17，27，38，45第四趟： 9，13，17，27，29，35，38，45，52，60第四趟归并完毕，排序结束。四、算法填空（每空2分，共20分）请在下面各个算法的空白处填上相应的语句，以实现算法功能。每个空白处只能填一个语句。1、 循环队列Q的队首元素出队操作算法。Q.front=Q.rearQ.front=(Q.front+1)%Max_Queue_Size ;2、 二叉树中序遍历的非递归算法。p=stacktop-p=p-Rchildbool!=0 3、 折半查找算法。Mid=(Lo

25、w+High)/2return(0)4、 简单选择排序算法。L-Rn.keyRk.keyk!=mL-Rk=L-R0五、编写算法（要求给出相应的数据结构说明，14分）解：结点类型定义及算法如下：#define int ElemType typedef struct Lnode ElemType data; /* 数据域，保存结点的值 */struct LNode *next; /* 指针域 */LNode; /* 结点的类型 */void Delete_LinkList_Value(LNode *L) LNode *p=L-next, *q, *ptr ;ElemType k ;while (

26、p-next!=NULL) k=p-data ; ptr=p ; q=ptr-next ;while (q!=NULL) if (q-data=k) ptr-next=q-next ; free(q) ; /* 删除值相同的结点 */ptr=ptrnext ; q=ptrnext ; /* 继续检查后续结点 */p=p-next ; /* 继续检查下一结点，是否有值相同的结点 */算法分析：设单链表长度为n，若指针p指向第i(i1,n-1)个结点，则删除和指针p所指向结点值相同的结点时：比较次数为n-i，指针的移动次数为n-i，则总的比较次数为：i=1(n-i)=n(n-1)/2n-1所以，时间复杂度为：O(n2)