陕西师范大学200721数据结构复习资料

《数据结构》作业

一、选择题

1．线性表的顺序存储结构是一种    的存储结构，线性表的链式存储结构是一种　 的存储结构。

a.  随机存储； b.顺序存储； c. 索引存取； d. HASH存取

2．一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是      。

a. edcba;   b. decba;  c. dceab;  d.abcde

3．一个队列的入队序列是1，2，3，4，则队列的输出序列是            。

a. 4,3,2,1;  b. 1,2,3,4;   c. 1,4,3,2;   d.3,2,4,1

4．在一个单链表中，已知p结点是q结点的直接前驱结点，若在p和q之间插入结点s，则执行的操作是     。

a.   s->nxet=p->next; p->next=s;

b.   p->next=s->next;  s->next=p;

c.   q->next=s;  s->next=p;

d.   p->next=s;   s->next=q;

5．设有两个串p,q，求q在p中首次出现的位置的运算称作        。

a.联接        b.模式匹配     c.求子串        d.求串长

6．二维数组M的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要          个字节。

a.   90        b.180           c.240           d.540

7．在线索二叉树中，结点p没有左子树的充要条件是       。

a.   p->lch==NULL

b.   p->ltag==1

c.   p->ltag==1且p->lch=NULL

d.   以上都不对

8．在栈操作中，输入序列为（A，B，C，D），不可能得到的输出序列为：______

A、（A，B，C，D）              B、（D，C，B，A）

C、（A，C，D，B）              D、（C，A，B，D）

9．已知某二叉树的后序序列是dabec，中序序列是debac，则它的先序序列是           。

A、acbed         B、decab       C、deabc         D、cedba

10．设矩阵A是一个对称矩阵，为了节省存储空间，将其下三角部分（见下图）按行序存放在一维数组B[1..n(n-1)/2]中，对任一上三角部分元素，在一维数组B的存放位置是     。

A、                B、

C、                   D、

11． 图G中有n个顶点，n-1条边，那么图G一定是一棵树吗？             。

A、  一定是                       B、一定不是                        C、不一定

12． 用某种排序方法对关键字序列{25，84，21，47，15，27，68，35，20}进行排序时，元素序列的变化情况如下：

   ① {25，84，21，47，15，27，68，35，20}

   ② {20，15，21，25，47，27，68，35，84}

   ③ {15，20，21，25，35，27，47，68，84}

   ④ {15，20，21，25，27，35，47，68，84}

   则所采用的排序方法是              。

A、  快速排序                     B、希尔排序

C、归并排序                      D、选择排序

13．表达式a*(b+c)-d的后缀表示式是     。

a. abcd-*+; b. abc+*d-; c. abc*+d-; d. -*a+bcd;

14．在双向循环链表中的结点P之后插入结点S的操作是        。

a.  p->next=s;   s->prior=p;     p->next->prior=s;    s->next=p->next;

b.  p->next=s;    p->next->prior=s;   s->prior=p;   s->next=p->next;

c.  s->prior=p;   s->next=p->next;   p->next=s;    p->next->prior=s;

d.  s->prior=p;   s->next=p->next;   p->next->prior=s;  p->next=s;

15．如下图所示循环队列，其中的数据元素个数是               

b.  (Q.rear-Q.front+m)%m

c.  Q.rear-Q.front

d.  Q.rear-Q.front+1

e.  (Q.rear-Q.front)%m

16．串是一种特殊的线性表，其特殊性体现在     。

a.   可以顺序存储

b.   数据元素是一个字符

c.   可以链接存储

d.   数据元素可以是多个字符

17． 数组A中，每个元素A[i][j]的长度是3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组的单元数是     。

a.   80

b.   100

c.   240

d.   270

18．已知某二叉树的先序遍历序列是abdgcefh，中序遍历序列是dgbaechf，则其后序遍历的结点访问顺序序列是           。

a.   bdgcefha

b.   gdbecfha

c.   bdgaechf

d.   gdbehfca

19．线索二叉树是一种             结构。

a.   逻辑

b.   逻辑和存储

c.   物理

d.   线性

20．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的          倍。

a.   1/2

b.   1

c.   2

d.   3

21．采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定元素所在的块时，则每块应分为          个元素的块时，查找效率最佳。

a.   10

b.   25

c.   6

d.   625

22．一个栈的输入序列是12345，则栈的不可能输出序列是            。

a.   54321

b.   45321

c.   43512

d.   12345

23． 完全二叉树一定是满二叉树吗？      。

a.   一定是

b.   不是

c.   不一定

24．线性表采用链式存储结构时其地址        。

a.   必须是连续的

b.   部分地址必须是连续的

c.   一定是不连续的

d.   连续不连续都可以

25． 具有线性结构的数据结构是            。

a.   树

b.   图

c.   广义表

d.   栈

26．下图为顺序队列的初始情况，设a, b, c相继出队列，e, f相继入队列，则指针Q.front和Q.rear分别为               。

Q.rear=4	5
	4
d	3
c	2
Q.front=0 b	1
a	0

a.   2,5

b.   3,5

c.   3,6

d.   4,6

27、线性表若采用链式存储结构时，要求内存中可用存储单元的地址   

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

 C、一定是不连续的               D、连续不连续都可以

28、已知L是带表头结点的非空单链表，p为中间结点，要删除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

29、广义表 ((a)) 的表头是     ，表尾是     。

A、a                             B、(a)     

B、()                             D、((a))    

30设只含根结点的二叉树的高度为1，则高度为k的二叉树的最大结点数为       。

A.2^k

B.2^k-1

C.2^k-1

D.2^k-1-1

31有n个结点的完全二叉树中，从根开始对结点进行编号，根的编号为1，编号的方法是从上而下，从左至右，则编号最小的叶子结点的编号是          。

    A.

    B.

    C.

    D.

二、填空题

1．设n行n列的下三角阵A已经压缩存储到一维数组S[0..]中，若按行序为主序存储，则A[i][j]对应的在S中的存储位置是              。

2．广义表（（a），（（b），c），（（（d））））的长度是         ，深度是           。

3．深度为k的完全二叉树至少有     个结点，至多有        个结点，若按自上而下，从左到右的次序给结点编号（从1开始），则编号最小的叶子结点的编号是       。

4．根据有向图的宽度优先遍历算法，对下图2所示有向图从顶点v1出发进行搜索，所得到的顶点遍历序列是               。

0	V1	2 1 3    NULL 3 4    NULL 1 3    NULL
1	V2	NULL
2	V3
3	V4	NULL
4	V5

                               图2

5．有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为82的元素时，需要经过     次比较就找到。

6．_____________是数据的最小单位。

7．在双向链表中，每个结点有两个指针域，一个是指向_____________,另一个指向_________。

8．设栈ST用顺序存储结构表示，则栈ST为空的条件是____________________。

9．两个串相等的充分必要条件是_____________________和对应位置上的字符相等。

10．对于深度为h的二叉树至多有___________个结点。

11．将一个A的对称矩阵压缩存储到一个一维数组中，该数组的长度至少为__________。

12、在线形表的顺序存储结构中，逻辑上相邻的元素在物理位置上__________相邻。

13、栈的特点是_________________,队列的特点是___________________.

三、算法应用题

1．数据集{4，5，6，7，10，12，18}为结点权值构造Huffman树，请给出构造所得的Huffman树，并求其带权路径长度。

2．假设一棵二叉树的先序序列是EBADCFHGIKJ，中序序列是ABCDEFGHIJK。请画出该二叉树。

3．已知一颗二叉排序树如下图所示，若依次删除93、19、87、48结点，试分别画出每删除一个结点后得到的二叉排序树。

4．已知关键字序列{19，01，23，14，55，20，84，27，68，11，10，77}，采用哈希函数：H(key)=key%13，和开放地址法的线性探测再散列方法解决冲突，已知其装填因子，试对该关键字序列构造哈希表，并求其查找成功时的平均查找长度。

5．画出和下列已知序列对应的森林F:

森林的先序遍历序列是：ABCDEFGHIJKL；

森林的中序遍历序列是：CBEFDGAJIKLH。

6．假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10。请给这8个字母设计哈夫曼编码。

①　给出其邻接矩阵，并按Prim算法求其最小生成树；

②　给出其邻接表，并按Kruskal算法求其最小生成树。

8．我们已经知道对长度为n的记录序列进行快速排序时，所需进行的比较次数依赖于这n个元素的初始排列。试问：

①   n=7时在最好情况下需进行多少次比较?请说明理由。

②   对n=7给出一个最好情况的初始排列实例。

9．下列算法为斐波那契查找算法：

int  FibSearch (SqList  r, KeyType  k)

{

    j=1;

while (fib(j)

mid=n-fib(j-1)+1; //若fib(j)=n+1, 则mid=fib(j-1)

f1=fib(j-2);   f2=fib(j-3);   found=false;

while ( (mid!=0) && (!found) )

switch

{

  case  (k==r[mid].key): found=true;  break;

  case  (k

    if (!f2) mid=0;

    else{ mid=mid-f2;  t=f1-f2;  f1=f2;  f2=t; }

    break;

  case  (k>r[mid].key):

    if (f1==1) mid=0;

    else { mid=mid+f2; f1=f1-f2;  f2=f2-f1; }

    break;

}

        if found return mid;

        else  return 0;

    }//FibSearch

    其中fib(i)为斐波那契序列。试画出对长度为20的有序表进行斐波那契查找的判定树，并求其等概率时查找成功的平均查找长度。

10．对下图所示的AOE网络，计算各活动的最早开始时间e (i)和最迟开始时间l (i)，各事件的最早发生时间ve(i)和vl(i)；并列出各条关键路径。

11、设s=‘i am a student’，t=‘good’,q=‘worker’,

求：strlength(s);     substr(s,8,7);         index（s,’a’）;    replace(s,’student’,q);     concat(substr(s,6,2),concat(t,substr(s,7,8)))。

四、算法设计题

1．设线性表，试写一按下列规则和并为线性表的算法，即使得

  当时；

或者   当时。

线性表和均以单链表作存储结构，且表利用表和表中的结点空间构成。

注意：单链表的长度值和均未显示存储。

2．试完成二叉树按层次（同一层自左至右）遍历的算法。

3．试完成求无向图的连同分量个数的算法。

4．试写一算法将两个递增有序的带头结点的单链表合并为一个非递增有序的带头结点的单链表。(利用原表结点空间)

5．设顺序表va中的数据元素递增有序（数据元素的类型是整型）。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。

7．以单链表作存储结构实现直接选择排序，排序的结果使得单链表的关键字按升序排列。

五、简答题

1．画出广义表（a,(b,(c,())),(d,e),((f))）的存储图。（链式）

2．分别画出具有3个结点的树和具有3个结点的二叉树的所有形态。

六、证明题

1．试证明：若借助栈由输入序列得到的输出序列为 (它是输入序列的一个排列)，则在输出序列中不可能出现这样的情况：存在使得 。

2．试证明：在一棵满k叉树上的叶子结点数和非叶子结点数之间满足一下关系：

七、应用题

1．已知BST树如下图所示，画出删除关键字为42的数据元素后的结果。