《数据结构与算法的习题》由会员分享，可在线阅读，更多相关《数据结构与算法的习题（7页珍藏版）》请在金锄头文库上搜索。
1、分数评卷人一、单项选择题 ：（本大题共 20 小题，每题 2 分，共 30 分）（说明：将答案写在试卷后面的答题纸上）1.计算机识别、存储和加工处理的对象被统称为( ) A.数据 B.数据元素 C.数据结构 D.数据类型 2.在具有 n 个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是( ) A.O(1) B.O(n) C.O(nlogn) D.O(n2) 3.队和栈的主要区别是( ) A.逻辑结构不同 B.存储结构不同 C.所包含的运算个数不同 D.限定插入和删除的位置不同 4.链栈与顺序栈相比，比较明显的优点是( ) A.插入操作更加方便 B.删除操作更加方便 C.不会出现
2、下溢的情况 D.不会出现上溢的情况 5.下列说法中正确的是（） A. 二叉树中任何一个结点的度都为 2 B. 二叉树的度为 2 C. 任何一棵二叉树中至少有一个结点的度为 2 D. 一棵二叉树的度可以小于 2 6.在一非空二叉树的中序遍历序列中，根结点的右边（） A. 只有右子树上的所有结点 B. 只有右子树上的部分结点 C. 只有左子树上的所有结点 D. 只有左子树上的部分结点 7.在一个具有 N 个顶点的无向完全图中，包含的边的总数是（） A. N(N-1)/2 B. N(N-1) C. N(N+1) D. N(N+1)/2 8.下面的程序在执行时，S 语句共执行的（）次。 i=1; wh
3、ile (inext) Q=L;L=L-next;P=L;while(P-next) P=P-next; P-next=Q;Q-next=null; return ok; （2）写出下列程序段的输出结果（栈的元素类型 SElemType 为 char） 。 void main（） stack S;char x,y; initstack(S); x=c;y=k; Push(S,x); Push(S,a); Push(S,y); Pop(S,x); Push(S,t); Push(S,x); Pop(S,x); Push(S,s); while(!stackempty(S) pop(S,y);pr
4、intf(y) ; ; printf(x); （3）简述以下算法的功能（栈和队列的元素类型均为 int） void algo3(Queueint d;initstack(S); while(!Queueempty(Q) dequeue(Q,d);push(S,d); while(!stackempty(S) pop(S,d);enqueue(Q,d); （4）简述以下算法的功能（栈的元素类型 SElemType 为 int） 。 status algo2（stack S, int e） stack T;int d; initstack(T); while(! Stackempty(S) pop
5、(S,d); if(d!=e) push(T,d); while(!Stackempty(T) pop(T,d); push(S,d); （5）写出下列程序段的输出结果（队列中的元素类型 qelemtype 为 char） void main( ) Queue Q;initqueue(Q); char x=e,y=c; enqueue (Q,h) ;enqueue(Q,r) ;enqueue(Q,y) ; dequeue(Q,x) ; enqueue(Q,x) ; dequeue(Q,x) ; enqueue(Q,a) ; while( !Queueempty(Q) dequeue(Q,y)
6、; printf(y) ; printf(x) ; 得分评卷人复查人五、编程应用题（本大题共 5 小题，第 39、40、41 小题每 小题 6 分，第 42、43 小题每小题 10 分，共 38 分）（1）试写一个算法，自大至小依次输出顺序读入的三个整数 X,Y 和 Z 的值。 （2）试编写算法，将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多 项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间构成这两个链表。 （3）试将下列递推过程改写为递归过程。 void ditui(int n) int i; i=n; while (i1)printf(i-); 2已知二叉树的先序序列和中序序列分别为 HDACBGFE 和 ADCBHFEG，画出该二叉树；3.编写一个计算二叉树的深度的算法4.请回答下列问题：(1)英文缩写DAG的中文含义是什么？(2)请给出下面DAG图的全部拓扑排序。
