数据结构期末考试模拟试题

1、数据结构被形式地定义为（D, R），其中D是          的有限集合，R是D上的         有限集合。

2、一个算法的效率可用            、            来衡量。

3、向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动         个元素。

4、具有n个叶子结点的哈夫曼树，其结点总数是      个。

5、一般情况下，快速排序的时间复杂度是          。

6、向栈中压入元素的操作是先          ，后           。

7、            称为空串；              称为空白串。

8、采用三元组表存储稀疏矩阵，三元是指        。

9、具有10个结点的完全二叉树，其深度是         。

10、线性有序表（a1，a2，a3，…，a20）是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索      次。

11、散列法（哈希）存储的基本思想是由         决定数据的存储地址。

12、具有n个顶点的无向图，最多有         条边；如果该图是一个连通图，那它最少有      条边；其生成树有       条边。

13、每个结点的平衡因子             的二叉排序树称为平衡二叉树，中序遍历该树可得到                。

14、

二、判断题（正确的画√，错误的画Χ；每题1分，共10分）

1、队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。

2、根据二叉树的先序和中序遍历结果，可唯一确定该二叉树。  

3、栈和队列的存储方式既可是顺序方式，也可是链接方式。  

4、二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。  

5、一个有向无环图进行拓扑排序，结果可能不唯一。 

6、链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动将

后续各个单元向前移动。 

7、用二叉链表存储包含n个结点的二叉树，结点的2n个指针域中有n+1个为空指针。

8、具有2个结点的二叉树有2种形态。

9、线性表在链式存储时，逻辑上相邻的元素在存储的物理位置次序上也一定不相邻。

10、顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。

三、单项选择题（每小题2分，共30分）

1、算法分析的目的是        。

  A、分析算法的易读性

  B、研究算法中输入和输出的关系

  C、分析算法的效率，以求改进

  D、找出合理的数据结构

2、对图进行深度优先搜索时，使用的辅助存储结构是        。

A、栈       B、队列     C、链表      D、数组

3、在一个单链表中，在p之后插入s所指结点，则执行        。

  A、s->link=p; p->next=s;

  B、s->link=p->link; p->link=s;

  C、s->link=p->link; p=s;

  D、p->link=s; s->link=p;

4、在循环链表中，first为指向链表表头的指针，current为链表当前指针，在循环链表中检测current是否达到链表表尾的语句是        。

  A、current->link==NULL B、first->link==current

  C、first==current          D、current->link==first

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

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

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

6、比较次数与序列的原始状态(原始排列)无关的排序方法是        排序方法。

A、插入           B、选择        C、冒泡           D、快速

7、如果结点a有3个兄弟，而且b为a的双亲，则b的度为        。

A、３　　　　B、４　　   C、５　　　　D、２

8、进栈序列为（A,B,C），不可能的出栈序列是        。

A、(A,B,C)     B、(C,B,A)      C、(A,C,B)      D、(C,A, B)

9、不稳定的排序方法是      。

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

C、快速排序             D、基数排序

10、设单链表中指针p指着结点a，若要删除a之后的结点（若存在），则需要修改指针的操作为        。

A、p->next=p->next->next         B、p=p->next

C、p= p->next->next　　　　  D、p->next=p

11、对5个不同的数据元素进行直接插入排序，最多需要进行        次比较。

A、10           B、14         C、15           D、25

12、具有n个顶点的完全无向图，有      条边。

A、n(n-1)               B、n(n+1)

C、n(n-1)/2             D、n(n+1)/2

13、采用分块查找方法进行查找，既要有利于数据文件的动态变化，又要具有良好的查找效率，数据文件应选择         。

A、块内、块间顺序存储结构              B、块内、块间链式存储结构

C、块内顺序、块间链式存储结构        D、块内链式、块间顺序存储结构

14、已知A=(a,b), B=(A,A),那么GetHead(GetHead(GetTail(B)))=   。

A、(a)            B、A             C、a              D、(A) 

15、一个n*n的对称矩阵，若以行为主序压缩存入一维数组，数组的容量为        。

A、n*n         B、n*n/2        C、n*（n+1）/2     D、（n+1）*（n+1）/2

四、解答题（共30分）

1、已知如图所示的带权图:

①求每个顶点的度（本小题2分）

②画出该图对应的邻接矩阵（本小题4分）

③求该图的最小生成树（本小题4分）

2、根据查找表（19, 14, 23, 01, 68, 20, 84, 27）

①构造一棵二叉排序树（本小题4分）

②计算查找成功时的平均查找长度（本小题3分）

③中序遍历所得的二叉树（本小题4分）

④将该树转换成对应的森林（本小题4分）

3、对集合（19, 14, 23, 01, 68, 20, 84, 27），以19为枢轴元素，画出一趟快速排序的过程（本小题5分）

五、算法设计题（共10分）

1、在一个带头结点的单链表上删除第i个结点（本小题6分）。

status Del_LinkList(LinkList &L, int i, ElemType &e)

{  

p=L; 

2、将折半查找算法补充完整(本小题4分)。

int Search_Half(SSTable st,KeyType key)

{  low=1;  high=st.Length;

   while(    ①    )

    {    mid=     ②    ;

        if(st.elem[mid].key==key) return mid;

        else if(st.elem[mid].key              else       ④       ;

}

return 0;

}    

参

一、填空题（每空1分，共20分）

1、数据元素，关系

2、时间复杂度，空间复杂度

3、n-i+1

4、2n-1               

5、nlogn

6、将元素置于栈顶，栈顶指针加1           

7、不包含任何字符的字符串，仅由空格字符组成的字符串

8、 元素的行号、列号、值

9、4

10、5

11、哈希函数

12、n(n-1)/2   ，n-1，n-1

13、绝对值不超过1，非递减排列的有序序列

二、判断题（每题1分，共10分）  

2、3、5、7正确，其余的错。

三、单选（每题2分，共30分）

CABDD  BBDCA  BCDCC

四、解答题（30分）

1、①(2分)   

TD(v1)=3  TD(v2)=3  TD(v3)=5  TD(v4)=3  TD(v5)=3  TD(v6)=3

②(4分)

0  2  1  5  #  #

2  0  5  #  3  #

1  5  0  3  4  4

5  #  3  0  #  2

#  3  4  #  0  5

#  #  4  2  5  0

③(4分)

2、

① （4分）19

14            23

01           20          68

                    27           84             

②(4分)ASL=(1+2*2+3*3+4*2)/8=11/4

③（3分）01,14,19,20,23,27,68,84

④（4分）

19     23       68     84

14     20       27      

01           

3、（5分）

五、算法设计题（6+4分）

1、

j=0;

while(p->next && j{ p=p->next; j++;

}

if(!(p->next)||j>I-1) return error;

q=p->next;p->next=q->next;

e=q->data;free(q);

return ok; 

} 

2、low<=high

(low+high)/2

low=mid+1

high=mid-1