枣庄学院数据结构

一、单项选择题:下面每题的选项中，只有一个是正确的（本题共10小题，每小题2分，共20分）

1．数据结构是一门研究数据组织、 C 和运算等的一般方法的学科。 【A】结构 【B】关系 【C】存储 【D】映像 2．在数据结构中数据的逻辑结构包括 D 。

【A】线性结构 【B】树形结构 【C】图形结构 【D】ABC都是 3．

算法必须具备的五个特性是 B 和输入、输出 。

【A】. 可执行性、可移植性、可扩充性 【B】. 可行性、确定性、有穷性 【C】. 确定性、有穷性、稳定性 【D】. 易读性、稳定性、安全性 4．

对三维数组，设c1=c2=c3 =1, d1=d2=d3= 5, L=1, Loc(1,1,1)=1000, 则

Loc(2,3,4) = D 。

【A】. 1030 【B】. 1034 【C】. 1036 【D】. 1038 解：Loc( a234 )

= Loc(a111)+ L*[(d2-c2+1)*(d3-c3+1)*(j1-c1)+ (d3-c3+1) (j2-c2) + (j3-c3)] =1000++1*[(5-1+1)*(5-1+1)*(2-1)+ (5-1+1)*(3-1)+(4-1)] =1000+[5*5*1+5*2+3] =1038

第1页 共2页

5． 设栈的入栈序列是1234，则不可能的出栈序列是 B 。

【A】. 4321 【B】. 1234 【C】. 1432 【D】. 4231 6．

已知广义表L=( (x, y, z),(o, p, q)) , 则 head ( tail (head ( tail (L)) )) 的值是

B 。

【A】. y 【B】. p 【C】. ( ) 【D】. o 7．

队列的特性是 A 。

【A】. 先进先出 【B】. 先进后出 【C】. 随意出入 8．

在带头结点的非空单链表中，在p指针所指的结点之后删除一个结点q的

操作是 B 。

【A】. p→next = q; free(q); 【B】. q→next = p→next→next；free(q); 【C】. q→next = p→next ; p=q; 【D】. p→next = q; free(q) ; 9．一棵深度为5的二叉树至多有___C__个结点。

【A】. 16 【B】. 32 【C】.31 【D】. 10

至多有N=2K-1

10．一棵3个结点的二叉树最多有 A 种形态。 【A】. 5 【B】. 3 【C】. 6 【D】. 4

二、 （本题满分10分）

设有数据逻辑结构为：

B=(K, R)

K={K1,K2,K3,K4,K5,K6,K7,K8,K9}

R={, , , , , , ,

第2页 共2页

}

试给出此数据逻辑结构的图示，并指出它属于何种结构

三、（本题满分10分）

稀疏矩阵一般采用何种压缩存储方法（写出两种），并画出下列稀疏矩阵A的三元组和十字链表表示。

5002215013300A00060000009106028  

第3页 共2页

四、（本题满分15分）

已知二叉树的前序和中序遍历序列ABCDEFGHIJ和BCDAFEHJG （1）试画出该二叉树并写出其后序遍历序列； （2）画出该二叉树中序遍历序列的线索二叉树 答：后序遍历序列DCBFIJHGEA

第4页 共2页

五、（本题满分10分）

证明：一棵n(n0)个结点构成的二叉树中最多有2 证明：深度为k的满二叉树有个结点 即n=2k-1, n+1=2k

log(n1)log2k klog(n1)

又性质1， 第k层上最多有 2k12log(n1)1个（叶结点）。 N0= (n+1)/2个叶结点

六、（本题满分12分）

设有一以head为头指针的带头结点的单链表，链表中的结点信息均为整数。 （1）画出上述单链表示意图；

（2）试写一函数删除单链表中所有结点信息为负数的结点。

第5页 共2页

log(n1)1 个叶结点。

第6页 共2页