《数据结构期末试题1及答案》由会员分享，可在线阅读，更多相关《数据结构期末试题1及答案（8页珍藏版）》请在金锄头文库上搜索。
1、第 1 页（共 9 页）试卷 A 1、顺序表中所有结点的类型必须相同。 （ ）2、链接表中所有灵活利用存储空间，所以链表都是紧凑结构。 ( ）3、用 Ch1，Ch2 表示两个字符，若 Ord(Ch1)Ord(Ch2)，则称Ch1Ch2 4、Shell 排序方法是不稳定的 。 （ ）5、只允许最下面的二层结点的度数小于 2 的二叉树是完全二叉树( ) 6、若检索所有结点的概率相等，则内部路径长度大的二叉树其检索效率高。 （ ） 7、n 个结点的有向图，若它有 n(n1)条边，则它一定是强连通的。8、广义表中，若限制表中成分的共享和递归所得到的结构是树结构 ）9、多维数组元素之间的关系是线性的。
2、（ ）10、任何无环的有向图，其结点都可以排在一个拓扑序列里。 ( ) 11、数据的逻辑结构可形式地用一个二元组 B(K，R)来表示，其中 K 是_，R 是_。 12、广义表(a,(a,b),d,e,(i,j),k)的长度是 。 13、一个串，除自身之外的所有子串都是该串的 。 14、树形选择排序总的时间开销为 。 15、按先根次序法周游树林正好等同于按 周游对应的二叉 树。第 2 页（共 9 页）16、外部路径长度 E 定义为从扩充二叉树的 到每个 的路径长度之和。 17、在图结构中，如果一个从 Vp到 Vq的路径上除 Vp和 Vq可以相同外， 其它结点都不相同，则称此路径为一 称为回路。
3、18、栈是一种 表。 19带权的 又称为网络。 20、nn 的三对角矩阵按“行优先顺序”存储其三对角元素，已和 a11 的存储地址为 LOC(a11)，矩阵的每个元素占一个存储单元，则 aij(i1，j=1，2 或 1in，ji1，i，i1 或 in，jn1，n)的存储地址为 LOC(aij) 。21、对于单链表形式的队列，队空的条件是 （ ）A、 FRnil B、 FR C、 Fnil 且 Rnil D、 RF122、下述排序算法中，稳定的是 （ ）A、 直接选择排序 B、 表插入排序 C、 快速排序 D、 堆排序 23、四组含 C1C7的结点序列中，哪一种是下列有向图的拓扑序列（ ）A、C
4、1，C2，C6，C7，C5，C4，C3 B、 C1，C2，C6，C3，C4，C5，C7第 3 页（共 9 页）C、 C1，C4，C2，C3，C5，C6，C7 D、 C5，C7，C4，C1，C2，C6，C324、下列广义表中，长度为 2 的有（ ）A(a，b) B(c，(a，b)，d) C(c，(a，b) D(a，b)，(c，(a，b) A A，C A，B A，B ，C，D25、树最适合用来表示( )。A 、有序数据元素 B 、无序数据元素C 、元素之间具有分支层次关系的数据 D、 元素之间无联系的数据26、判定一个栈 ST(最多元素为 m0)为空的条件是( )。A、ST-top!=0 B、 S
5、T-top=0C、ST-top!=m0 D、 ST-top=m0 27、在一个单链表中，若删除p所指结点的后续结点，则执行( )。A、p-next=p-next-next;B、 p=p-next;p-next=p-next-next;C、 p-next=p-next; D、 p=p-next-next 28、递归函数f(n)=f(n-1)+n(n1)的递归体是( )。A、 f(1)=0 B、 f(0)=1C、 f(n)=f(n-1)+n D、 f(n)=n 29、广义表(a,b),c,d)的表尾是( )。A 、a B 、b C、 (a,b) D 、(c,d) 30、在线索化二叉树中，t所指结点
6、没有左子树的充要条件是( )。A、t-left=NULL B、t-ltag=1C、t-ltag=1 且 t-left=NULL D、以上都不对31、在双链表中，要在指针变量 P 所指结点之后插入一个新结点，请第 4 页（共 9 页）按顺序写出必要的算法步骤。(设：P 所指结点不是链表的首尾结点，q 是与 p 同类型的指针变量) 32、已知待排序文件各记录的排序码顺序如下72 73 71 23 94 16 05 68请列出快速排序过程中每一趟的排序结果。 33、已知一查二叉树的中序序列为 cbedahgijf,后序序列为 cedbhjigfa,画出该二叉树，并且写出该二叉树的先序序列。34、画出
7、下列网络的最小生成树。5、画出广义表 W(X(W，a，Y(W)，Y(W) 的双链图表示36、下面给出了起泡排序算法，请填写算法中的空框，使算法正确。struct node int key;datatype info; node,*lnode；int i，j;int flag;node X;node Rn; 每循环一次作一次起泡循环 i 以 1 为步长，从 1 到 n1，执行下列语句(1)( )第 5 页（共 9 页）(2)循环 j 以 1 为步长，( )，执行若( )Rj.key则 flag 1；XRj；( )；Rj1 X(3)若( )则跳出循环 算法结束37、下面给出了在对称序穿线树中找指定
8、结点在后序下的前驱算法，请填写算法中的空框，使算法正确。struct node datatype info;node *llink，*rlink; *lnode；lnode p; p 指向指定结点lnode q; q 指向指定结点在后序下的前驱 若 p-rlink0则( )，算法结束否则 q p (1) 循环 当( )时，反复执行( )(2) ( ) 算法结束第 6 页（共 9 页）A 卷一判断题（每小题判断题（每小题 1 1 分，共分，共 1010 分）分）1 2 3 4 56 7 8 9 10二填空题（每小题填空题（每小题 2 2 分，共分，共 2020 分）分）11结点的有穷集合、 K
9、上关系的有穷集合；125 13真子串； 14O(nlog2n)； 15前序法；16根、 外部结点 17简单路径； 18线性表；19连通图； 20Loc(a11)2*(i1)j1。三单项选择题（每小题单项选择题（每小题 2 2 分，共分，共 2020 分）分）21A 22B 23D 24 25、C 26、B 27、A 28、C 29、 D 30、B四、简答题（每小题简答题（每小题 6 6 分，共分，共 3030 分）分）31q=(linklist)malloc(sizeof(linklist)；q-llink p；q-rlink p-rlink；p-rlink-llink q；p-rlink q
10、。32答：各趟结果如下：68 05 71 23 16 72 94 7316 05 23 68 71 72 94 7305 16 23 68 71 72 94 73 第 7 页（共 9 页）05 16 23 68 71 72 94 73 05 16 23 68 71 72 94 73 05 16 23 68 71 72 73 94 05 16 23 68 71 72 73 9433答：node k1 k2 k3 k4 k5 k6key 2 4 6 9 11 16key mod 7 2 4 6 2 4 2node link01234567k17k6k25k5k3k43第 8 页（共 9 页）34答：35.答：五、算法设计题（每小题算法设计题（每小题 1010 分，共分，共 2020 分）分）36(1) flag 0；(2) 1 到 n-1；(3) Rj1.key；(4) Rj Rj1；(5) flag037(1) q p.rlink(2) q.link 0(3) q (1)*(q.llink)(4) q q.llink第 9 页（共 9 页）
