数据结构(C语言)试卷(6)

成都东软信息技术学院

200  ~200  学年第  学期期末试题——数据结构（C语言）

题号	一	二	三	四	五	总分
分数

说明：本试卷共五大题，试卷满分100分，考试时间120分钟。

一．单项选择题：共10小题、每题2分，满分20分；将答案填入题中的括号中。

1．在一个长度为n的顺序存储线性表中，删除第i个元素(1≤i≤n)时，需要从前向后依次前移        个元素。

        A、n-i       B、n-i+1        C、n-i-1       D、i

2.组成数据的基本单位是               。

       A、数据项   B、数据类型    C、数据元素   D、数据变量

3. 当利用大小为N的一维数组顺序存储一个栈时，假定用top=－1表示栈空，则向这个栈插入一个元素时，首先应执行        语句修改top指针。

       A．top++；          B．top--；         C．top=NULL ；        D．top；

4. 若让元素a，b，c依次进栈，则出栈次序不可能出现         种情况。

       A．cba        B．bac      C．cab      D．acb

5. 线性表采用链式存储时，其地址     。

       A．必须是连续的     B．部分地址必须是连续的

       C．一定是不连续的   D．连续与否均可以

6. 线性表的链式存储有利于      运算。

       A．插入  B．读表元    C．查找     D．定位

7. 在一个长度为n的线性表中插入第i个元素的操作中，i的取值范围是 

A．1≤i≤n  B．0≤i≤n    C．1≤i≤ n+1  D．1≤i≤n-1

8.如果要查找单链表中的第i个元素，应该从        开始进行查找。

A．第i个结点  B． 头结点  C． 尾结点   D． 任意一个结点

9.当采用顺序存储方式存储队列时，可能出现存储空间剩余，而不允许继续入队的情况，称为         。

A．溢出  B． 假溢出   C．队列不能用顺序存储方式    D．数组存储空间过小 

10.一棵完全二叉树的结点按层次遍历从1开始编号，如果编号为m的结点有双亲，则双亲的编号为         。

A．2×m  B．m＋1    C．m/2    D.m-1

二．判断题：共10小题，每小题1分，满分10分；请将答案以“√”、“×”形式填入题后括号中。

1.线性表不能采用链式存储。                                                （ ）

2.在单链表中插入结点主要通过移动元素实现。                                （ ）

3.栈是一种先进后出的线性表。                                             （ ）

4.在循环顺序队列中插入新元素不需要判断队列是否满了。                       （ ）

5.用头部插入结点的方法建立单链表时，插入元素的顺序和链表中的元素顺序相同。 （ ）

6. 一棵满二叉树一定是一棵完全二叉树。                                      （ ）

7. 线性表中的每个元素都有一个前驱元素和后继元素。                          （ ）

8.叶子结点的度不一定为0。                                                  （ ）

9.哈夫曼树得到的带权路径长度一定是最小的。                                  （ ）

10.有序表的折半查找只适用于升序表。                                          （ ）

三．填空题：共10小题，每题3分，满分30分；请将一个正确答案的序号填入括号中。

1. 数据结构中，非线性逻辑结构有            、         、         。

2.在长度为n的顺序表中插入第i个元素（假设i值可操作），要将元素从第    个到第   个元素向       （前或后）移动。

3.将指向单链表中的某个结点的指针p移动到该结点的后继结点表示为               。

4.在长度为Maxsize的循环队列中，删除一个新元素，修改front队头指针为          。 

5. 在链队列中，与入队相关的指针是           、与出队有关的指针是          （头指针或尾指针）。

6. 总共三层的完全二叉树，其结点数至少有        个，至多有           个。

7. 二叉树的遍历方法有        、          、          、             。

8. 二叉树的存储结构有          、          、          结构表示。

9.一棵哈夫曼树有5个叶子结点组成，该哈夫曼树总共有          个结点。

10．简单排序有          、            、              方法。

四．数据结构图形描述题：共3小题，每题10分，满分30分；根据题目画出示意图。

1.如图1，画出该二叉树的顺序存储示意图。

                       A

                 B    C

    D       E          F

               

                 G               H           （图1）

0     1     2    3     4    5    6     7     8    9    10   11   12    13   14

2.一棵二叉树的先序遍历序列为ABDGCEHF，中序遍历序列为DGBAEHCF，请画出该二叉树的示意图。

3.有一个初始序列为1，22，13，8的数据，要求写出该序列的冒泡排序示意图。

五．算法描述题：共1小题，每题10分，满分10分；用任何程序语言、伪语言或流程图描述下列算法。

1.如图2所示已知一个单链表指针Q指向某结点，M指向待插入的值为X的结点，要求将M结点插到Q结点的后一结点位置。

结点的结构为：

（1）请画出示意图

（2）描述算法。

    

          

          Q     M

200  ~200  学年第  学期期末试题——数据结构（C语言）

答题卡

题号	一	二	三	四	五	总分
分数

一．单项选择题：（2’×15）

1	2	3	4	5	6	7	8	9	10

二．判断题：(1’×10)

1	2	3	4	5	6	7	8	9	10

三．填空题：（2’×10）

1.          、             、             

2.         、           、                

3.                         

4.                  

5.           、              

6.           、              

7.           、              、                  、               

8.           、              、               

9.                

10.           、              、              

四．数据结构图形描述题：（10’ ×3）

1．

0     1     2    3     4    5    6     7     8    9    10   11   12    13   14

2．

3．

五．算法描述题：（10’）

1.

2005~2006学年第二学期期末试题——数据结构（C语言）

答案及评分标准

一．单项选择题：（2’×10）

1	2	3	4	5	6	7	8	9	10
A	A	A	C	D	A	C	B	B	C

二．判断题：(1’×10)

1	2	3	4	5	6	7	8	9	10
×	×	√	×	×	√	×	×	√	×

三、  填空题：（3’×10）

1.  集合         、     树       、     图         

2.     n      、       i+1       、       后       

3.      p=p->next      

4. front=(front+1)/Maxsize    

5.     尾指针      、     头指针         

6.    4       、    7        

7.  先序   、     中序     、    后序     、     层次          

8.     顺序存储     、     二叉链表存储        、    三叉链表存储    

9.      9        

10.   直接插入排序 、     冒泡排序      、    简单选择排序     

四．   数据结构图形描述题：（10’ ×3）

1.

A

B

C

∧

D

E

F

∧

∧

G

∧

∧

H

0     1     2    3     4    5    6     7     8    9    10   11   12    13   14

2.                  A

              B            C

         D           E          F

                G           H

3.                         1   22    13    8

第一趟   第一次比较        1   22

第二次比较、交换      13    22     

         第三次比较、交换             8     22

第二趟   第一次比较       1    13              

         第二次比较、交换      8     13

第三趟   第一次比较      1     8

算法结束，结果为         1     8      13      22

五．   算法描述题：（10’）

1．

    

    Q

    M

M—>next=Q—>next;

Q—>next=M;