算法与数据结构复习重点全

一、单项选择题（50个）

1. 数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称，而（B）是数据不分割的最小单位。 A． 数据元素 B．数据项 C．数据对象 D．数据结构 2.以下数据结构中，（A）是非线性数据结构 A.树 B.字符串 C.队 D.栈

3．在定义ADT时，除数据对象和数据关系外，还需说明（c）。

A． 数据元素 B．算法C．基本 D．数据项 4．算法分析的两个方面是（ C）。

A. 正确性和简明性 B. 可读性和文档性 C. 空间复杂性和时间复杂性 D. 数据复杂性和程序复杂性

5．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（B）。 A．数据具有同一特点

B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致 C．每个数据元素都一样

D．数据元素所包含的数据项的个数要相等 6．以下说法正确的是（D）。 A．数据元素是数据的最小单位 B．数据项是数据的基本单位

C．数据结构是带有结构的各个数据项的集合

D．一些表面上很不相同的数据可以有相同的逻辑结构

7. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（A）。 A. 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） B. 在第i个结点后插入一个新结点（1≤i≤n） C. 删除第i个结点（1≤i≤n） D. 将n个结点从小到大排序

8．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（B）。 A．p->next=s;s->next=p->next; B．s->next=p->next;p->next=s; C．p->next=s;p->next=s->next; D．p->next=s->next;p->next=s; 9．线性表L=(a1,a2, ??an)，下列陈述正确的是（D）。 A．每个元素都有一个直接前驱和一个直接后续 B．线性表中至少有一个元素

C．表中诸元素的排列必须是由小到大或由大到小

D．除第一个和最后一个元素外，其余每个元素都有且仅有一个直接前驱和直接后继

10．若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，则采用（D）存储方式节省时间。

单链表只有一个指针域，是指向直接后继的。没有指向直接前驱。 循环链表也是只指向直接后继。

只有双向链表有两个指针域，分别指向直接前驱和后继。要存取值得修改两个指针 顺序表是在计算机内存中以数组的形式保存的线性表。它是数组，不用考虑修改指针，只用修改下标

A．单链表 B．双链表 C．单循环链表 D．顺序表

11．在一个不设头结点的单链表L中，若要向表头处插入一个由指针p指向的结点，则执行（D）

你要明白，p是指针，L也是指针。如题意，不需要考虑表头的情况。开始时，链表的first节点是L，而我们需要将p插入到L之前。所以我们需要将p链接到L所指的内存上，p->link = L。然后，因为我们要保持链表L不变，也就说L指针是在表首的，所以说要把 这时链表的（表首指针）P的值赋给L指针。 A. L = p;p->next = L; C.p->next =L;p = L;

B. p->next = L->next; L->next = p; D. p->next =L; L = p;

12．双向链表中插入一个结点需要修改( D )个指针。 4，2

在双向链表的结点A和B之间插入结点P需要修改： P的前驱，P的后继，A的后继，B的前驱

在单向链表的结点A和B之间插入结点P需要修改： P的后继，A的后继

A．1 B．2 C．3 D．4

13.在长度为n的顺序存储的线性表中，删除第i个元素(0 <= i <= n-1)时，需要从前向后依次前移（A）个元素。

删除第i个元素时,后面的元素ai+1~an都要向上移动一个位置,共移动了n-i个元素 A．n-iB. n-i+1 C. n-i-1 D. i

14．对于一个头指针为L的带头结点的单链表，判定该表为空表的条件是（B）。 A．L==NULL B．L→next==NULL C．L→next==L D．L!=NULL

15.若编号为1，2，3，4，5，6的六节车厢依次通过一段栈形轨道，则在出口处不可能得到（D）

A．143562 B．456321 C．145326 D．426531

16.若已知一个栈的入栈序列是1，2，3，?，n，其输出序列为p1，p2，p3，?，pn，若p1=n，则pi为（C）。

A．iB．n=iC．n-i+1D．不确定

17.判定一个队列QU（最多元素为m0）为满队列的条件是（A）。

队满条件是元素个数为m0。由于约定满队时队首指针与队尾指针相差1，所以不必再减1了，应当选A。当然，更正确的答案应该取模，即：QU->front = = (QU->rear+1)% m0 A．QU->rear － QU->front = = m0 B．QU->rear － QU->front －1= = m0 C．QU->front = = QU->rear D．QU->front = = QU->rear+1

18.假设一个循环顺序队列的队首和队尾指针分别为front和rear，存储空间大小为n，则判断队空的条件是（B）

A．( front + 1 ) % n == rearB．front == rear C．( rear + 1 ) % n == frontD．front == 0

19．栈和队列都是（c）

A．顺序存储的线性结构 B. 链式存储的非线性结构 C. 限制存取点的线性结构 D. 限制存取点的非线性结构

20．设栈S和队列Q的初始状态均为空，元素a,b,c,d,e,f,g依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b,d,c,f,e,a,g,则栈的容量至少是（3） 首先明确几个概念：栈是先进后出，队列是先进先出；题目中指定了进栈顺序，但没说要连续进栈。(下面箭头图中右代表栈底，左代表栈顶，队列同样) 假如栈的容量是1，则第一个出栈的肯定是a，不符合；

假如栈的容量是2，则a、b进去，b出栈，c进栈，只能c先出栈，d不可能出队顺序在c前

假如栈的容量是3，分析过程如下： ①S：b→a，b出栈，Q：b，S：a

②S：d→c→a，d、c依次出栈，Q：c→d→b，S：a

③S：f→e→a，f、e、a依次出栈，Q：a→e→f→c→d→b，S：null ④S：g，g出栈，Q：g→a→e→f→c→d→b，S：null Q中元素依次出队，即b→d→c→f→e→a→g

A．1 B.2 C. 3 D. 4

21．在目标串T[0?n-1]=‘acaabab’中，对模式串p[0?m-1]=‘ab’进行子串定位操作的

结果（A） A.3

B.4

C.5

D.6

22．设有两个串 p 和 q ，其中 q 是 p 的子串，求 q 在 p 中首次出现的位置的算法称为（c）。

A．求子串 B．联接 C．匹配 D．求串长

23．设有串t='I am a good student '，那么SubString(t,6,6)=（D）。 A. student B. a good s C. good D. a good 24.如下陈述中正确的是（A）

A. 串是一种特殊的线性表 B. 串的长度必须大于零 C. 串中元素只能是字母 D. 空串就是空白串

25.二维数组A按行顺序存储，其中每个元素占1个存储单元。若A[1][1]的存储地址为420，A[3][3]的存储地址为446，则A[5][5]的存储地址为（c） A.470

B.471 C.472

D.473

26.设有一8×8对称矩阵A[5][5]，采用按行压缩存储的方式存放在一维数组B[ ]中，则数组B[ ]的容量至少需要( B )个元素空间。 A.25 B.26 C.16 D.15

27.已知广义表的表头为A，表尾为(B,C)，则此广义表为（b） A.（A,(B,C)）

B.（A,B,C）

C.(A,B,C)

D.(( A,B,C))

28．已知广义表: A=(a,b), B=(A,A), C=(a,(b,A),B), 求下列运算的结果: GetTail(GetHead(GetTail (C))) =( D )。 A.(a) B. A C. a D. (A) 29.下列关于二叉树的说法中正确的是( C )

A．二叉树是度为2的树。B．有n个结点的二叉树高度为log2n C.有10个叶子结点的二叉树中有9个度为2的结点。 D. 二叉树中至少有一个度为2的结点

30．设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（a）。

根据二叉树与森林的对应关系，将森林F转换成对应二叉树B的规则如下：1、若森林F为空，则二叉树B为空。2、若森林F非空，则F中的第一棵树的根为二叉树B的根；第一棵树的左子树所构成的森林按规则转换成一个二叉树成为B的左子树，森林F的其他树所构成的森林按本规则转换成一个二叉树成为B的右子树。依此规则可知：二叉树B结点的个数减去其右子树的结点的个数就是森林F的第1棵树的结点的个数。 A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定

31．一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结点有( A)个。 33个，

二叉树性质3 在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则no=n2+1。

由n0=n2+1, n0+n2=67,得 n2 = 33

A． 33 B．34 C． 32 D． 30

32．已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于(B )

A．1.0 B．2.9 C．3.4 D．5.5

33．给定权值集合{ 2, 3, 5, 6, 8 }，则构造的Huffman树的带权路径长度为（D）。 A． 48

B．55

C．54

D． 53

34．5个字符有如下4种编码方案，是前缀编码的是C）。

A．01,0000,0001,001,1 B．011,000,001,010,1 C．000,001,010,011,100 D．0,100,110,1110,1100

35.利用二叉链表存储树，则根结点的右指针是（C）。【青岛大学 2001 五、5 （2分）】

A．指向最左孩子 B．指向最右孩子 C．空 D．非空 36.一个有n个顶点和n条边的无向图一定是（D）。 A. 连通的 B. 不连通的 C. 无环的 D. 有环的

37．已知有向图G = ( V, E )，其中V = {V1, V2, V3, V4, V5, V6, V7 }，E = { , ,

, , , , , , }，G的拓扑序列是（A）。 A．V1V3V4V6V2V5V7 B．V1V3V2V6V4V5V7C．V1V3V4V5V2V6V7

D．V1V2V5V3V4V6V7

38．如下图所示由7个结点组成的无向图，对它进行深度优先遍历，不可能得到的顶点序列是（B）。

A.1427653B.1245367 C. 1342765D. 1534267

1354276 39.在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( D )

无向的邻接矩阵一定是对称阵。当vi与vj中间有一条边相连接时，则a(ij)=1,否则为0.e条边对应了n个顶点的度的和为2e.所以零元素的个数为n^2-2e A．e B．2e C．n2－e D．n2－2e

40.在含n个顶点和e条边的连通图中,其生成树顶点数和边数分别为( C ) A．n,e B．n,e-1 C．n,n-1 D．n-1,e-1

（1）画出无向图G。 （2）画出G的邻接表

7.设某带权无向图如下图，画出用Prim算法和Kruskal算法，从顶点A开始生成最小生成树的每一步结果。并求出最小生成树的带权路径长度。

A138E45F95B2D7C6 8．下面的邻接表表示一个给定的无向图 （1）画出其邻接矩阵存储；

（2）给出从顶点v1开始,对图G用深度优先搜索法进行遍历时的顶点序列； （3）给出从顶点v1开始,对图G用广度优先搜索法进行遍历时的顶点序列。 0123456 1 2 3 4 5 6 7 1 1 0 0 1 1 34 2 2 1 5 6 3 4

9.假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：

①画出描述折半查找过程的判定树； ②若查找元素54，需依次与哪些元素比较？ ③若查找元素90，需依次与哪些元素比较？

④假定每个元素的查找概率相等，求查找成功时的平均查找长度。 （1）

折半查找判定树为

（2） 查找元素54，需依次与30，63，42，54比较 （3） 查找元素90，需依次与30，63，87，95比较 （4） ASL=1/12*（1+2*2+4*3+5*4）=3

10．给定一组整数26，9，34，62，30，23，请构造一棵二叉排序树。，并计算查找成功时的ASL。

11.试画出从空树开始，由字符序列(t,d,e,s,u,g,b,j,a,k,r,i)构成的二叉平衡树，为每一次的平衡处理指明旋转类型，并计算出在等概率情况下查找成功时的平均查找长度。

12.设散列表长13，散列函数为H(key) = key % 13，对关键字序列93, 63, 81, 78, 17, 8, 85, 7, 30, 22造表，用线性探测再散列法解决冲突，画出相应的散列表，并计算等概率下查找成功时的平均查找长度。

13.设散列表长13，散列函数为H(key) = key % 13，对关键字序列19，14，23，1，68，20，84，27，55，11，10，79造表，用拉链法解决冲突，画出相应的散列表，并计算等概率下查找成功时的平均查找长度。

14．已知一组元素的关键码为 ( 77, 16, 48, 21, 19, 51, 62, 37, 60, 22, 99, 66 )，利用Shell排序使之按关键字递增次序排序，设排序间隔分别是5、3、1，依次写出各趟排序后的结果。 15. 给定一个关键字序列{24，19，32，43，38，6，13，22}，请写出冒泡排序各趟的排序结果。

五、算法设计（6个） 1. 简述以下算法的功能 Status

A(LinkedList L) {

if (L&&L->next){ Q=L;L=L->next;P=L; While(P-> next) P=P-> next;

P-> next= Q; Q-> next=NULL; }

return OK ; }

2.写出下列程序段的输出结果（栈的元素类型SElem Type为char）。 void main( ){ Stack S; Char x,y; InitStack(S); X=’c’;y=’k’;

Push(S,x); Push(S,’a’); Push(S,y); Pop(S,x); Push(S,’t’); Push(S,x); Pop(S,x); Push(S,’s’);

while(!StackEmpty(S)){ Pop(S,y);printf(y); }; Printf(x); }

输出为“stack”。

Pop()函数是出栈并且将出栈的元素存放在第二个行参里，所以在这里x的值不再是c了，而是出栈的元素。。 过程：

首先是三个压栈操作，之后栈里的元素为：cak，左边的为栈底，右边是栈顶。

然后一个出栈，此时栈里的元素为：ca，x中存的是k； 之后两次压栈，此时栈里的元素为：catk；

之后一个出栈，此时栈里的元素为：cat，x中存的是k；

最后一次压栈，此时栈里的元素为：cats，x中存的是k； 之后while(!StackEmpty(S)){ Pop(S,y);printf(y); }; 结果是stac， Printf(x); 结果是k，

3．简述以下算法的功能（栈和队列的元素类型均为int）。 voidnizhi(Queue &Q){ Stack S; int d; InitStack(S);

while(!QueueEmpty(Q)){ DeQueue (Q,d); Push(S,d);}; while(!StackEmpty(S)){ Pop(S,d); EnQueue (Q,d); }} 功能：队列中的数据元素逆置 4．已知二叉树的结点数据类型如下： typedefstruct node {ElemType data;

//数据元素

struct node *lchild; //指向左孩子 struct node *rchild; //指向右孩子

}BTNode,*BiTree;

阅读下列二叉树算法,回答问题。 voidexchange(BiTreebt) { if(bt) {BiTree s;

s=bt->lchild; bt->lchild=bt->rchild;bt->rchild=s; exchange(bt->lchild); exchange(bt->rchild); } }

该算法执行二叉树运算的什么功能？

将二叉树中所有结点的左，右子树相互交换

5．将下面算法填完整。

intSearch_Bin(SSTable ST, KeyType key){

//在有序表ST中折半查找其关键字等于key的数据元素，若找到，则返回该元素//在表中的位置，否则返回0 low=1;high=; while(low<=high){ mid=____________;

if(EQ(key, ST.elem[mid].key)) return ____________; else if(LT(key, ST.elem[mid].key)) high=____________; else low=____________; }

return ____________;

intSearch_Bin(SSTableST,KeyType key)

//在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为 //该元素在表中的位置，否则为0. {

low = 1; high = ST.length; while(low <= high) {

mid = (low + high)/2;

if(EQ(key, ST.elem[mid].key)) return mid;

else if (LT(key,ST.elem[mid].key)) high = mid -1;

else low = mid + 1; }

return 0;

}//Search.Bin

6.试写出改进的冒泡排序算法描述，当某一趟排序没有数据交换时结束排序过程

public static void bubbleSort_2(int[] list) { int temp = 0; // 用来交换的临时数 boolean bChange = false; // 交换标志

// 要遍历的次数

for (int i = 0; i < list.length - 1; i++) { bChange = false;

// 从后向前依次的比较相邻两个数的大小，遍历一次后，把数组中第i小的数放在第i个位置上

for (int j = list.length - 1; j > i; j--) { // 比较相邻的元素，如果前面的数大于后面的数，则交换 if (list[j - 1] > list[j]) { temp = list[j - 1]; list[j - 1] = list[j]; list[j] = temp; bChange = true; } }

// 如果标志为false，说明本轮遍历没有交换，已经是有序数列，可以结束排序 if (false == bChange) break; } }

// 从后向前依次的比较相邻两个数的大小，遍历一次后，把数组中第i小的数放在第i个位置上

for (int j = list.length - 1; j > i; j--) { // 比较相邻的元素，如果前面的数大于后面的数，则交换 if (list[j - 1] > list[j]) { temp = list[j - 1]; list[j - 1] = list[j]; list[j] = temp; bChange = true; } }

// 如果标志为false，说明本轮遍历没有交换，已经是有序数列，可以结束排序 if (false == bChange) break; } }

本文来源：https://www.bwwdw.com/article/q9co.html