2024年1月4日发(作者：)

试卷 A

1、顺序表中所有结点的类型必须相同。 （ ）

2、链接表中所有灵活利用存储空间，所以链表都是紧凑结构。 ( ）

3、用Ch1，Ch2表示两个字符，若Ord(Ch1)＜Ord(Ch2)，则称Ch1＜Ch2

4、Shell排序方法是不稳定的 。 （ ）

5、只允许最下面的二层结点的度数小于2的二叉树是完全二叉树( )

6、若检索所有结点的概率相等，则内部路径长度大的二叉树其检索效率高。 （ ）

7、n个结点的有向图，若它有n(n－1)条边，则它一定是强连通的。

8、广义表中，若限制表中成分的共享和递归所得到的结构是树结构 ）

9、多维数组元素之间的关系是线性的。 （ ）

10、任何无环的有向图，其结点都可以排在一个拓扑序列里。 ( )

11、数据的逻辑结构可形式地用一个二元组B＝(K，R)来表示，其中K是__________，R是_____________。

12、广义表(a,(a,b),d,e,((i,j),k))的长度是 。

13、一个串，除自身之外的所有子串都是该串的 。

14、树形选择排序总的时间开销为 。

15、按先根次序法周游树林正好等同于按 周游对应的二叉树。

16、外部路径长度E定义为从扩充二叉树的 到每个

的路径长度之和。

17、在图结构中，如果一个从Vp到Vq的路径上除Vp和Vq可以相同外，其它结点都不相同，则称此路径为一 称为回路。

18、栈是一种 表。

19．带权的 又称为网络。

20、n×n的三对角矩阵按“行优先顺序”存储其三对角元素，已和a11的存储地址为LOC(a11)，矩阵的每个元素占一个存储单元，则aij(i＝1，j=1，2或1＜i＜n，j＝i－1，i，i＋1或i＝n，j＝n－1，n)的存储地址为LOC(aij)＝ 。

第 1 页（共 8 页）

21、对于单链表形式的队列，队空的条件是 （ ）

A、 F＝R＝nil B、 F＝R

C、 F≠nil且R＝nil D、 R－F＝1

22、下述排序算法中，稳定的是 （ ）

A、 直接选择排序 B、 表插入排序

C、 快速排序 D、 堆排序

23、四组含C1～C7的结点序列中，哪一种是下列有向图的拓扑序列（ ）

A、C1，C2，C6，C7，C5，C4，C3

B、 C1，C2，C6，C3，C4，C5，C7

C、 C1，C4，C2，C3，C5，C6，C7 D、 C5，C7，C4，C1，C2，C6，C3

24、下列广义表中，长度为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，D

25、树最适合用来表示( )。

A 、有序数据元素 B 、无序数据元素

C 、元素之间具有分支层次关系的数据

第 2 页（共 8 页）

D、 元素之间无联系的数据

26、判定一个栈ST(最多元素为m0)为空的条件是( )。

A、ST->top!=0 B、 ST->top==0

C、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(n>1)的递归体是( )。

A、 f(1)=0 B、 f(0)=1

C、 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所指结点没有左子树的充要条件是( )。

A、t->left==NULL B、t->ltag==1

C、t->ltag==1且t->left==NULL D、以上都不对

31、在双链表中，要在指针变量P所指结点之后插入一个新结点，请按顺序写出必要的算法步骤。

(设：P所指结点不是链表的首尾结点，q是与p同类型的指针变量)

32、已知待排序文件各记录的排序码顺序如下

72 73 71 23 94 16 05 68

请列出快速排序过程中每一趟的排序结果。

33、已知一查二叉树的中序序列为cbedahgijf,后序序列为cedbhjigfa,画出该二叉树，并且写出该二叉树的先序序列。

34、画出下列网络的最小生成树。

第 3 页（共 8 页）

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 R[n];

① [每循环一次作一次起泡]

循环 i以1为步长，从1到n－1，执行下列语句

(1)( )

(2)循环 j以1为步长，( )，执行

若( )＜R[j].key

则flag ← 1；

X←R[j]；( )；R[j＋1] ← X

(3)若( )

则跳出循环

第 4 页（共 8 页）

② 算法结束

37、下面给出了在对称序穿线树中找指定结点在后序下的前驱算法，请填写算法中的空框，使算法正确。

struct node {

datatype info;

node *llink，*rlink;

} *lnode；

lnode p; [p指向指定结点]

lnode q; [q指向指定结点在后序下的前驱]

① 若p->rlink＞0

则( )，算法结束

否则q ← p

② (1) 循环 当( )时，反复执行

( )

(2) ( )

③ 算法结束

A 卷

一．判断题（每小题 1 分，共 10 分）

1．× 2．× 3．√ 4．√ 5．×

6．× 7．√ 8．√ 9．× 10．√

第 5 页（共 8 页）

二．填空题（每小题 2 分，共 20 分）

11．结点的有穷集合、 K上关系的有穷集合；

12．5 13．真子串； 14．O(n·log2n)； 15．前序法；

16．根、 外部结点 17．简单路径； 18．线性表；

19．连通图； 20．Loc(a11)＋2*(i－1)＋j－1。

三．单项选择题（每小题 2 分，共 20 分）

21．A 22．B 23．D 24．④ 25、C

26、B 27、A 28、C 29、 D 30、B

四、简答题（每小题 6 分，共 30 分）

31．q=(linklist)malloc(sizeof(linklist)；

q->llink ← p；

q->rlink ← p->rlink；

p->rlink->llink ← q；

p->rlink ← q。

32．答：各趟结果如下：

[68 05 71 23 16] 72 [94 73]

[16 05 23] 68 [71] 72 [94 73]

[05] 16 [23] 68 [71] 72 [94 73]

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 94

33．答：

第 6 页（共 8 页）

node k1 k2 k3 k4 k5 k6

key 2 4 6 9 11 16

key mod 7 2 4 6 2 4 2

0

1

2

3

4

5

6

7

k4

node link

7

∧

5

∧

∧

3

k1

k6

k2

k5

k3

34．答：

35.答：

第 7 页（共 8 页）

五、算法设计题（每小题 10 分，共 20 分）

36．(1) flag ← 0；

(2) 1到n-1；

(3) R[j＋1].key；

(4) R[j] ← R[j＋1]；

(5) flag＝0

37．(1) q ← p↑.rlink

(2) q.↑link ＜ 0

(3) q ← (－1)*(q↑.llink)

(4) q ← q↑.llink

第 8 页（共 8 页）