数据结构习题集1

《数据结构》练习册

陕西理工学院计算机系 数据结构精品课建设小组编

计算机科学与技术系

前 言

《数据结构》练习册按照《数据结构》课程的教学大纲编著，分为九章，主要题型包括：选择题、判断题、填空题和程序题，每章都从基础出发，有少部分难度较大题型。编写的目的是为了给学生提供一个练习和提高的平台。可作为我校计算机科学与技术、信息系统与信息管理与网络工程本科专业学生的辅助教材使用。由于编写时间较仓促，有错误在所难免，敬请教师和学生提出宝贵意见。

计算机科学与技术系《数据结构》课程组

2006年8月

第一章 绪 论

一、选择题

1.组成数据的基本单位是（ ） A．数据项 B．数据类型 C．数据元素 D．数据变量 2.数据结构是研究数据的（ ）以及它们之间的相互关系。 A．理想结构，物理结构 B．理想结构，抽象结构 C．物理结构，逻辑结构 D．抽象结构，逻辑结构 3.在数据结构中，从逻辑上可以把数据结构分成（ ）。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构

4.数据结构是一门研究非数值计算的程序设计问题中计算机的 （①）以及它们之间的（②）和运算等的学科。

①A．数据元素 B．计算方法 C．逻辑存储 D．数据映像 ②A．结构 B．关系 C．运算 D．算法 5.算法分析的两个主要方面是（ ）。 A．数据复杂性和程序复杂性 B．正确性和简明性 C．可读性和简明性 D．空间复杂性和时间复杂性 6.算法分析的目的是（ ）。 A．找出数据结构的合理性 B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进 D．分析算法的易懂性和文档性 7.计算机算法指的是（①）,它必须具备输入、输出和（②）等5个特性。 ①A．计算方法 B．排序方法 C．解决问题的有限运算序列 D．调度方法 ②A．可执行性，可移植性和可扩充性 B．可行性，确定性和有穷性 C．确定性、有穷性和稳定性 D．易读性、稳定性和安全性 二、判断题

1.数据的机内表示称为数据的存储结构。（ ） 2.算法就是程序。（ ）

3.数据元素是数据的最小单位。（ ）

4.算法的五个特性为：有穷性、输入、输出、完成性和确定性。（ ） 5.算法的时间复杂度取决于问题的规模和待处理数据的初态。（ ） 三、填空题

1.数据逻辑结构包括________、________、________和________四种类型,其中树形结构和图形结构合称为________。

2.在线性结构中,第一个结点________前驱结点,其余每个结点有且只有________个前驱结点；最后一个结点________后续结点,其余每个结点有且只有________个后续结点。

3.在树形结构中,树根结点没有________结点,其余每个结点有且只有________个前驱结点；叶子结点没有________结点,其余每个结点的后续结点可以________。

4.在图形结构中,每个结点的前驱结点数和后续结点数可以________。

5.线性结构中元素之间存在________关系,树形结构中元素之间存在________关系,图形结构中元素之间存在________关系。

6.算法的五个重要特性是________、________、________、________、________。 7.数据结构的三要素是指________、________和________。

8.链式存储结构与顺序存储结构相比较,主要优点是________________________________。

1

9.设有一批数据元素,为了最快的存储某元素,数据结构宜用________结构,为了方便插入一个元素,数据结构宜用________结构。

四、算法分析题

1.求下列算法段的语句频度及时间复杂度 for(i=1; i<=n; i++) for(j =1; j <=i ; j++) x=x+1;

分析：该算法为一个二重循环，执行次数为内、外循环次数相乘，但内循环次数不固定，与外循环有关，因些，时间频度T(n)=1+2+3+…+n=n*(n+1)/2

有 1/4≤T(n)/n2≤1，故它的时间复杂度为Ｏ(n2), 即Ｔ(n)与n2 数量级相同。 2.分析下列算法段的时间频度及时间复杂度 for （i=1;i<=n;i++） for (j=1;j<=i;j++) for ( k=1;k<=j;k++) x=i+j-k;

分析算法规律可知时间频度T(n)=1+(1+2)+(1+2+3)+...+(1+2+3+…+n) 由于有1/6 ≤ T（n）/ n3 ≤1，故时间复杂度为Ｏ(n3)

第二章 线性表

一、选择题

1.一个线性表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是( )。 A．110 B．108 C．100 D．120

2.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ ）个元素。

A．64 B．63 C．63.5 D．7 3.线性表采用链式存储结构时，其地址（ ）。 A．必须是连续的 B．部分地址必须是连续的 C．一定是不连续的 D．连续与否均可以

4.在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（ ）。 A．s->next=p;p->next=s; B．s->next=p->next;p->next=s; C．s->next=p->next;p=s; D．p->next=s;s->next=p; 5.在一个单链表中，若删除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; 6.下列有关线性表的叙述中，正确的是（ ）。 A．线性表中的元素之间隔是线性关系 B．线性表中至少有一个元素

C．线性表中任何一个元素有且仅有一个直接前趋 D．线性表中任何一个元素有且仅有一个直接后继 7.线性表是具有n个（ ）的有限序列（n≠0)。 A．表元素 B．字符 C．数据元素 D．数据项 二、判断题

1.线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。（ ） 2.如果没有提供指针类型的语言，就无法构造链式结构。（ ）

3.线性结构的特点是只有一个结点没有前驱，只有一个结点没有后继，其余的结点只有一个前驱和后继。（ ）

2

4.语句p=p->next完成了指针负值并使p指针得到了p指针所指后继结点的数据域值。（ ） 5.要想删除p指针的后继结点，我们应该执行q=p->next ； p->next=q->next； free(q)。（ ） 三、填空题

1.已知P为单链表中的非首尾结点，在P结点后插入S结点的语句为：________。

2.顺序表中逻辑上相邻的元素物理位置( )相邻， 单链表中逻辑上相邻的元素物理位置________相邻。

3.线性表L＝（a1，a2，...，an）采用顺序存储，假定在不同的n＋1个位置上插入的概率相同，则插入一个新元素平均需要移动的元素个数是________。

4.在非空双向循环链表中，在结点q的前面插入结点p的过程如下：

p->prior=q->prior; q->prior->next=p; p->next=q; ________;

5.已知L是无表头结点的单链表，是从下列提供的答案中选择合适的语句序列，实现： 表尾插入s结点的语句序列是________。 A．p->next=s; B．p=L; C．L=s; D．p->next=s->next; E．s->next=p->next; F．s->next=L; G．s->next=null; H．while(p->next!=0) p=p->next; I．while(p->next!=null) p=p->next; 四、算法设计题

1.试编写一个求已知单链表的数据域的平均值的函数（数据域数据类型为整型）。

2.已知带有头结点的循环链表中头指针为head,试写出删除并释放数据域值为x的所有结点的c函数。

3.某百货公司仓库中有一批电视机，按其价格从低到高的次序构成一个循环链表，每个结点有价格、数量和链指针三个域。现出库（销售）m台价格为h的电视机，试编写算法修改原链表。

4.某百货公司仓库中有一批电视机，按其价格从低到高的次序构成一个循环链表，每个结点有价格、数量和链指针三个域。现新到m台价格为h的电视机，试编写算法修改原链表。

5.线性表中的元素值按递增有序排列，针对顺序表和循环链表两种不同的存储方式，分别编写C函数删除线性表中值介于a与b（a≤b）之间的元素。

6.设A=(a0,a1,a2,...,an-1),B=(b0,b1,b2,...,bm-1)是两个给定的线性表,它们的结点个数分别是n和m,且结点值均是整数。

若n=m，且 ai= bi （0≤i

若存在一个j， jB。 试编写一个比较A和B的C函数，该函数返回 -1或 0或 1，分别表示 AB。 7.试编写算法,删除双向循环链表中第k个结点。

8.线性表由前后两部分性质不同的元素组成(a0,a1,...,an-1,b0,b1,...,bm-1),m和n为两部分元素的个数,若线性表分别采用数组和链表两种方式存储,编写算法将两部分元素换位成(b0,b1,...,bm-1,a0,a1,...,an-1),分析两种存储方式下算法的时间和空间复杂度。

9.用循环链表作线性表(a0,a1,...,an-1)和（b0,b1,...,bm-1）的存储结构,头指针分别为ah和bh，设计C函数，把两个线性表合并成形如（a0,b0,a1,b1,…）的线性表，要求不开辟新的动态空间,利用原来循环链表的结点完成合并操作,结构仍为循环链表,头指针为head,并分析算法的时间复杂度。

3

10.试写出将一个线性表分解为两个带有头结点的循环链表，并将两个循环链表的长度放在各自的头结点的数据域中的C函数。其中,线性表中序号为偶数的元素分解到第一个循环链表中,序号为奇数的元素分解到第二个循环链表中。

11.试写出把线性链表改为循环链表的C函数。

12.己知非空线性链表中x结点的直接前驱结点为y,试写出删除x结点的C函数。

第三章 栈和队列

一、选择题

1.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（ ）。 A．edcba B．decba C．dceab D．abcde 2.栈结构通常采用的两种存储结构是（ ）。 A．线性存储结构和链表存储结构 B．散列方式和索引方式 C．链表存储结构和数组 D．线性存储结构和非线性存储结构 3.判定一个栈ST(最多元素为m0)为空的条件是（ ）。 A．ST-〉top!=0 B．ST-〉top==0 C．ST-〉top!=m0 D．ST-〉top=m0 4.判定一个栈ST(最多元素为m0)为栈满的条件是（ ）。 A．ST->top!=0 B．ST->top==0 C．ST->top!=m0-1 D．ST->top==m0-1 5.一个队列的入列序列是1,2,3,4,则队列的输出序列是（ ）。 A．4,3,2,1 B．1,2,3,4 C．1,4,3,2 D．3,2,4,1

6.循环队列用数组A[0,m-1]存放其元素值，已知其头尾指针分别是front和rear则当前队列中的元素个数是（ ）。

A．(rear-front+m)%m B．rear-front+1 C．rear-front-1 D．rear-front 7.栈和队列的共同点是（ ） A．都是先进后出 B．都是先进先出 C．只允许在端点处插入和删除元素 D．没有共同点 8.表达式a*(b+c)-d的后缀表达式是（ ）。 A．abcd*+- B．abc+*d- C．abc*+d- D．-+*abcd

9.4个元素a1，a2，a3和a4依次通过一个栈，在a4进栈前，栈的状态，则不可能的出栈序是（ ）。

A．a4，a3，a2，a1 B．a3，a2，a4，a1 C．a3，a1，a4，a2 D．a3，a4，a2，a1

10.以数组Q[0..m－1]存放循环队列中的元素，变量rear和qulen分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数，队列第一个元素的实际位置是（ ）。

A．rear－qulen B．rear－qulen＋m C．m－qulen D．1＋（rear＋m－qulen）%m 二、填空题

1.栈的特点是________，队列的特点是________。

2.线性表、栈和队列都是________结构,可以在线性表的________位置插入和删除元素，对于栈只能在________插入和删除元素，对于队列只能在________插入元素和________删除元素。

3.一个栈的输入序列是12345,则栈有输出序列12345是________。(正确/错误)

4.设栈S和队列Q的初始状态皆为空，元素a1，a2，a3，a4，a5和a6依次通过一个栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3，a5，a4，a6，a2，a1则栈S至少应该容纳________个元素。

三、算法设计题

4

1.假设有两个栈s1和s2共享一个数组stack[M],其中一个栈底设在stack[0]处，另一个栈底设在stack[M-1]处。试编写对任一栈作进栈和出栈运算的C函数push（x,i)和pop(i),i=l,2。其中i=1表示左边的栈，,i=2表示右边的栈。要求在整个数组元素都被占用时才产生溢出。

2．利用两个栈s1,s2模拟一个队列时,如何用栈的运算来实现该队列的运算?写出模拟队列的插入和删除的C函数。

一个栈s1用于插入元素,另一个栈s2用于删除元素。

第四章 串

一、选择题

1.下列关于串的叙述中，正确的是（ ） A．一个串的字符个数即该串的长度 B．一个串的长度至少是1 C．空串是由一个空格字符组成的串 D．两个串S1和S2若长度相同，则这两个串相等 2.字符串\的nextval值为( ) A．(0,1,01,1,0,4,1,0,1) B．(0,1,0,0,0,0,2,1,0,1) C．(0,1,0,1,0,0,0，1,1) D．(0,1,0,1,0,1,0,1,1)

3.字符串满足下式,其中head和tail的定义同广义表类似,如head(?xyz?)=?x?,tail(?xyz?)= ?yz?,则s=( )。concat(head(tail(s)),head(tail(tail(s))))= ?dc?。

A．abcd B．acbd C．acdb D．adcb 4.串是一种特殊的线性表,其特殊性表现在（ ） A．可以顺序存储

B．数据元素是一个字符 C．可以链式存储

D．数据元素可以是多个字符 5．设串S1=?ABCDEFG?,s2=?PQRST?,函数CONCAT（X，Y）返回X和Y串的连接串，SUBSTR（S，I，J）返回串S从序号I开始的J个字符组成的字串，LENGTH（S）返回串S的长度，则CONCAT（SUBSTR（S1，2，LENGTH（S2）），SUBSTR（S1，LENGTH（S2），2））的结果串是（ ）。

A．BCDEF B．BCDEFG C．BCPQRST D．BCDEFEF 二、算法设计

1.分别在顺序存储和一般链接存储两种方式下,用C语言写出实现把串s1复制到串s2的串复制函数strcpy(s1,s2)。

2.在一般链接存储(一个结点存放一个字符)方式下,写出采用简单算法实现串的模式匹配的C语言函数int L_index(t,p)。

第五章 数组与广义表

一、选择题

1．常对数组进行的两种基本操作是（ ） A．建立与删除 B．索引和修改 C．查找和修改 D．查找与索引 2.二维数组M的元素是4个字符(每个字符占一个存储单元)组成的串,行下标i的范围从0到4,列下标j的范围从0到5,M按行存储时元素M[3][5]的起始地址与M按列存储时元素( )的起始地址相同。

A．M[2][4] B．M[3][4] C．M[3][5] D．M[4][4]

3.数组A[8][10]中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,存放该数组至少需要的单元数是（ ）。

A．80 B．100 C．240 D．270

4.数组A[8][10]中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,该数组按行存放时,元素A[7][4]的起始地址为（ ）。

A．SA+141 B．SA+144 C．SA+222 D．SA+225

5

5.数组A[8][10]中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,该数组按列存放时,元素A[4][7]的起始地址为（ ）。

A．SA+141 B．SA+180 C．SA+222 D．SA+225 6.稀疏矩阵一般的压缩存储方法有两种,即（ ）。

A．二维数组和三维数组 B．三元组和散列 C．三元组和十字链表 D．散列和十字链表

7.若采用三元组压缩技术存储稀疏矩阵,只要把每个元素的行下标和列下标互换,就完成了对该矩阵的转置运算,这种观点（ ）。

A．正确 B．错误

8.设矩阵A是一个对称矩阵,为了节省存储,将其下三角部分按行序存放在一维数组B[1,n(n-1)/2]中,对下三角部分中任一元素ai,j(i<=j),在一组数组B的下标位置k的值是（ ）。

A．i(i-1)/2+j-1 B．i(i-1)/2+j C．i(i+1)/2+j-1 D．i(i+1)/2+j 二、填空题

1.己知二维数组A[m][n]采用行序为主方式存储,每个元素占k个存储单元,并且第一个元素的存储地址是LOC(A[0][0]),则A[0][0]的地址是________。

2.二维数组A[10][20]采用列序为主方式存储,每个元素占一个存储单元,并且A[0][0]的存储地址是200,则A[6][12]的地址是________。

3.有一个10阶对称矩阵A,采用压缩存储方式(以行序为主,且A[0][0]=1),则A[8][5]的地址是________。

4.设n行n列的下三角矩阵A已压缩到一维数组S[1..n*(n+1)/2]中,若按行序为主存储,则A[i][j]对应的S中的存储位置是________。

5.若A是按列序为主序进行存储的4×6的二维数组,其每个元素占用3个存储单元,并且A[0][0]的存储地址为1000,元素A[1][3]的存储地址为________，该数组共占用________个存储单元。

三、算法设计

1.如果矩阵A中存在这样的一个元素A[i][j]满足条件:A[i][j]是第i行中值最小的元素,且又是第j列中值最大的元素,则称之为该矩阵的一个马鞍点。编写一个函数计算出1×n的矩阵A的所有马鞍点。

算法思想：依题意,先求出每行的最小值元素,放入min[m]之中,再求出每列的最大值元素,放入max[n]之中,若某元素既在min[i]中,又在max[j]中,则该元素A[i][j]便是马鞍点,找出所有这样的元素,即找到了所有马鞍点。

2.n只猴子要选大王,选举办法如下:所有猴子按1,2,...,n编号围坐一圈,从1号开始按1、2、...、m报数,凡报m号的退出到圈外,如此循环报数,直到圈内剩下只猴子时,这只猴子就是大王。n和m由键盘输入,打印出最后剩下的猴子号。编写一程序实现上述函数。

算法思想:本题用一个含有n个元素的数组a,初始时a[i]中存放猴子的编号i,计数器似的值为0。从a[i]开始循环报数,每报一次,计数器的值加1,凡报到m时便打印出a[i]值(退出圈外的猴子的编号),同时将a[i]的值改为O(以后它不再参加报数),计数器值重新置为0。该函数一直进行到n只猴子全部退出圈外为止,最后退出的猴子就是大王。因此,现本题功能的程序如下:

3.数组和广义表的算法验证程序 编写下列程序:

(1)求广义表表头和表尾的函数head()和tail()。 (2)计算广义表原子结点个数的函数count_GL()。

(3)计算广义表所有原子结点数据域(设数据域为整型〉之和的函数sum_GL()。 #include \#include \typedef struct node

6

{ int tag; union

{struct node *sublist; char data; }dd;

struct node *link; }NODE;

NODE *creat_GL(char **s) {

NODE *h; char ch; ch=*(*s); (*s)++; if(ch!='\\0') {

h=(NODE*)malloc(sizeof(NODE)); if(ch=='(') {

h->tag=1;

h->dd.sublist=creat_GL(s); } Else {

h->tag=0;

h->dd.data=ch; } } else

h=NULL; ch=*(*s); (*s)++; if(h!=NULL) if(ch==',')

h->link =creat_GL(s); else

h->link=NULL; return(h); }

void prn_GL(NODE *p) {

if(p!=NULL) {

if(p->tag==1) {

printf(\

7

if(p->dd.sublist ==NULL) printf(\ else

prn_GL(p->dd.sublist ); } else

printf(\ if(p->tag==1) printf(\if(p->link!=NULL) {

printf(\

prn_GL(p->link); } } }

NODE *copy_GL(NODE *p) {

NODE *q;

if(p==NULL) return(NULL);

q=(NODE *)malloc(sizeof(NODE)); q->tag=p->tag; if(p->tag)

q->dd.sublist =copy_GL(p->dd.sublist ); else

q->dd.data =p->dd.data; q->link=copy_GL(p->link); return(q); }

NODE *head(NODE *p) /*求表头函数 */ {

return(p->dd.sublist); }

NODE *tail(NODE *p) /*求表尾函数 */ {

return(p->link); }

int sum(NODE *p) /*求原子结点的数据域之和函数 */ { int m,n;

if(p==NULL) return(0); else

{ if(p->tag==0) n=p->dd.data; else

n=sum(p->dd.sublist); if(p->link!=NULL)

8

return; }

s[++top]=p; q=p; p=p->lchild; } p=s[top--]; q=p;p=p->rchild; }}

void lev_traverse(NODE *T) //按层次从上到下,每层从右到左的顺序列出二叉树所有结点的数据信息

{NODE *q[100],*p; int head,tail;

q[0]=T;head=0;tail=1; while(head

printf(\ if(p->rchild!=NULL) q[tail++]=p->rchild; if(p->lchild!=NULL) q[tail++]=p->lchild; }}

int depth(NODE *t) //求二叉树的深度 {

int num1,num2;

if(t==NULL) return(0);

if(t->lchild ==NULL&&t->rchild ==NULL) return(1); else {

num1=depth(t->lchild ); num2=depth(t->rchild ); if(num1>num2) return(num1+1); else

return(num2+1); } }

int onechild3(NODE *root) //非递归统计出二叉树共有多少个度为1的结点 { NODE *p,*s[100];

int top=0,num=0; //top为栈顶指针 p=root;

while((p!=NULL)||(top>0)) { while(p!=NULL)

{if(p->lchild!=NULL&&p->rchild==NULL ||p->lchild==NULL&&p->rchild!=NULL) num++;

s[++top]=p; p=p->lchild; } p=s[top--]; p=p->rchild; } return num; }

int like(NODE *t1,NODE *t2) //判定两颗二叉树是否相似

14

{

int like1,like2;

if(t1==t2&&t2==NULL) return(1); else

if(t1==NULL &&t2!=NULL||t1!=NULL&&t2==NULL) return(0); else {

like1=like(t1->lchild,t2->lchild); like2=like(t1->rchild ,t2->rchild ); return(like1&&like2); } }

char a[100]; //数组顺序存储二叉树

void change(NODE *t,int i) //将二叉树的链接存储转换为顺序存储 {

if(t!=NULL) {a[i]=t->data;

change(t->lchild,2*i); change(t->rchild,2*i+1); } }

int complete(NODE *t) //判断二叉树是否为完全二叉树 {

int i,flag=0; change(t,1);

for(i=1;i<100;i++)

{if(!flag&&a[i]=='\\0') flag=1; if(flag&&a[i]!='\\0') break; }

if(i==100) return(1); else return(0); }

第七章 图

一、判断题

1.一个无向图的邻接矩阵中各非零元素之和与图中边的条数相等。（ ） 2.一个有向图的邻接矩阵中各非零元素之和与图中边的条数相等。（ ） 3.一个对称矩阵一定对应着一个无向图。（ ）

4.一个有向图的邻接矩阵一定是一个非对称矩阵。（ ） 二、选择题

1.在一个图中,所有顶点的度数之和等于所有边数的（ ）倍。 A．1/2 B．1 C．2 D．4 2.在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。 A．1/2 B．1 C．2 D．4 3.一个有n个顶点的无向图最多有（ ）条边。 A．n B．n(n-1) C．n(n-1）/2 D．2n

15

4.具有4个顶点的无向完全图有（ ）条边。 A．6 B．12 C．16 D．20 5.具有6个顶点的无向图至少应有（ ）条边才能确保是一个连通图。 A．5 B．6 C．7 D．8 6.在一个具有n个顶点的无向图中,要连通全部顶点至少需要（ ）条边。 A．n B．n+1 C．n-1 D．n/2 7.对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小（ ） A．n B．(n-1) 2 C．n-1 D．n2

8.对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则表头向量的大小为（ ），所有邻接表中的结点总数是（ ）。

①A．n B．n+1 C．n-1 D．n+e ②A．e/2 B．e C．2e D．n+e 9.采用邻接表存储的图的深度优先遍历算法类似于二叉树的（ ）。 A．先序遍历 B．中序遍历 C．后序遍历 D．按层遍历 10.采用邻接表存储的图的宽度优先遍历算法类似于二叉树的（ ）。 A．先序遍历 B．中序遍历 C．后序遍历 D．按层遍历 11.判定一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以利用（ ）。 A．求关键路径的方法 B．求最短路径的Dijkstm方法 C．宽度优先遍历算法D．深度优先遍历算法

12.用Prim算法求下列连通的带权图的最小代价生成树，在算法执行的某刻，已选取的顶点集合U＝{1，2，5}，边的集合TE＝{（1，2），（2，5）}，要选取下一条权值最小的边，应当从（ ）组中选取。

3 12 A．{（1，4），（3，4），（3，5），（2，5）}

2 3 12 B．{（5，4），（5，3），（5，6）} 1 3 10 C．{（1，2），（2，3），（3，5）}

6 D．{（3，4），（3，5），（4，5），（1，4）} 5 11 7 三、填空题

6 1.n个顶点的连通图至少________条边。 4 5 4 2.在一个无环有向图G中，若存在一条从顶点i8 到顶点j的弧，则在顶点的拓扑序列中，顶点i与顶点j的先后次序是________。

3.在一个无向图的邻接表中，若表结点的个数是m，则图中边的条数是________条。 4. 如果从一个顶点出发又回到该顶点，则此路径叫做________。

5.如果从一无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是________。

6.若采用邻接表的存储结构，则图的广度优先搜索类似于二叉树的________遍历。

7. 一个连通图的生成树是该图的________连通子图。若这个连通图有n个顶点, 则它的生成树有________条边。

四、算法设计：

1.试在无向图的邻接矩阵和邻接链表上实现如下算法： (1)往图中插入一个顶点 (2)往图中插入一条边 (3)删去图中某顶点 (4)删去图中某条边

16

2.下面的伪代码是一个广度优先搜索算法，试以下图中的v0为源点执行该算法，请回答下述问题：

(1)对图中顶点vn+1，它需入队多少次？它被重复访问多少次?

(2)若要避免重复访问同一个顶点的错误，应如何修改此算法?

void BFS(ALGraph *G,int k)

{//以下省略局部变量的说明，visited各分量初值为假

InitQueue(&Q);//置空队列 EnQueue(&Q,k);//k入队 while(!QueueEmpty(&Q)){

i=DeQueue(&Q);//vi出队 visited[i]=TRUE;//置访问标记

printf(\访问vi for(p=G->adjlist[i].firstedge;p;p=p->next)

//依次搜索vi的邻接点vj(不妨设p->adjvex=j) if(!visited[p->adjvex])//若vj没有访问过

EnQueue(&Q,p->adjvex);//vj入队 }//endofwhile }//BFS

3.试以邻接表和邻接矩阵为存储结构，分别写出基于DFS和BFS遍历的算法来判别顶点vi和vj(i<>j)之间是否有路径。

4.试分别写出求DFS和BFS生成树(或生成森林)的算法，要求打印出所有的树边。 5.写一算法求连通分量的个数并输出各连通分量的顶点集。

6.设图中各边的权值都相等，试以邻接矩阵和邻接表为存储结构，分别写出算法： (1)求顶点vi到顶点vj(i<>j)的最短路径 (2)求源点vi到其余各顶点的最短路径

要求输出路径上的所有顶点(提示：利用BFS遍历的思想) 7.以邻接表为存储结构，写一个基于DFS遍历策略的算法，求图中通过某顶点vk的简单回路(若存在)。

8.写一算法求有向图的所有根(若存在)，分析算法的时间复杂度。

第八章 排 序

一、选择题

1.在所有排序方法中，关键字比较的次数与记录得初始排列次序无关的是（ ） A．希尔排序 B．起泡排序 C．插入排序 D．选择排序 2.设有1000个无序的元素,希望用最快的速度挑选出其中前10个最大的元素,最好（ ）排序法。 A．起泡排序 B．快速排序 C．堆排序 D．基数排序 3.在待排序的元素序列基本有序的前提下,效率最高的排序方法是（ ）。 A．插入排序 B．选择排序 C．快速排序 D．归并排序 4.一组记录的排序码为(46,79,56,38,40,84),则利用堆排序的方法建立的初始推为（ ）。 A．79,46,56,38,40,80 B．84,79,56,38,40,46 C．84,79,56,46,40,38 D．84,56,79,40,46,38

5.一组记录的关键码为(46,79,56,38,40,84),则利用快速排序的方法,以第一个记录为基准得到的一次划分结果为（ ）。

17

A．38,40,46,56,79,84 B．40,38,46,79,56,84 C．40,38,46,56,79,84 D．40,38,46,84,56,79

6.一组记录的排序码为(25,48,16,35,79,82,23,40,36,72),其中含有5个长度为2的有序表,按归并排序的方法对该序列进行一趟归并后的结果为（ ）。

A．16,25,35,48,23,40,79,82,36,72 B．16,25,35,48,79,82,23,36,40,72 C．16,25,48,35,79,82,23,36,40,72 D．16,25,35,48,79,23,36,40,72,82

7.排序方法中,从未排序序列中依次取出元素与己排序序列(初始时为空)中的元素进行比较,将其放入己排序序列的正确位置上的方法,称为（ ）。

A．希尔排序 B．起泡排序 C．插入排序 D．选择排序

8.排序方法中,从未排序序列中挑选元素并将其依次放入己排序序列(初始为空)的一端的方法,称为（ ）。

A．希尔排序 B．归并排序 C．插入排序 D．选择排序

9.用某种排序方法对线性表(25,84,21,47,15,27,68,35,20)进行排序时,元素序列的变化情况如下: (1)25,84,21,47,15,27,68,35,20 (2)20,15,21,25,47,27,68,35,84 (3)15,20,21,25,35,27,47,68,84 (4)15,20,21,25,27,35,47,68,845 则所采用的排序方法是（ ）。 A．选择排序 B．希尔排序 C．归并排序 D．快速排序 10.下述几种排序方法中,平均查找长度最小的是（ ）。 A．插入排序 B．选择排序 C．快速排序 D．归并排序 11.下述几种排序方法中,要求内存量最大的是（ ）。 A．插入排序 B．选择排序 C．快速排序 D．归并排序 12.快速排序方法在情况下最不利于发挥其长处。( ) A．要排序的数据量太大 B．要排序的数据中含有多个相同值 C．要排序的数据已基本有序 D．要排序的数据个数为奇数

13.设有10000个元素组成的无序序列,希望尽快挑选出其中前10个最大值元素,在不改变已有算法结构的前提下,以下几种内排序算法中( )最合适。

A．选择排序法 B．快速排序法 C．堆排序法 D．冒泡排序法 14.下列四种排序方法中，不稳定的方法是（ ） A．直接插入排序 B．冒泡排序 C．归并排序 D．直接选择排序 二、判断题

1.用直接选择排序方法分别对序列S1＝（1，2，3，4，5，6，7）和序列S2＝（7，5，3，2，4，1，6）进行排序，两者的比较次数不相同。（ ）

2.快速排序是所有排序中速度最快的一种。（ ）

3.堆排序是直到最后一趟排序结束之前所有元素才能在其最终的位置上。（ ） 三、填空题

1.试五种排序方法与对应的操作联系起来: (A)归并排序________ (B)选择排序________ (C)冒泡排序________ (D)插入排序________ (E)快速排序________

(1)从待排序序列中依次取出元素与己排序序列中的元素作比较将其放入己排序序列中的正确的位置上。

(2)从待排序序列中挑选元素,并将其放入己排序序列的一端。 (3)依次将相邻的有序表合并成一个有序表。

18

(4)每次把待排序的区间划分为左、右两个子区间,其中左区间中元素的键值均小于等于基准元素的键值,右区间中元素的键值均大于等于基准元素的键值。

(5)当两个元素比较出现反序(即逆序)时就相互交换位置。

2.在对一组记录（4,38,96,23,15,72,60,45,83）进行直接插入排序时,当把第7个记录60插入到有序表时,为寻找插入位置需比较________次。

3.在利用快速排序方法对一组记录(54,38,96,23,15,72,60,45,83)进行快速排序时,递归调用而使用的栈的所能达到的最大深度为________,共需递归调用的次数为________,其中第二次递归调用是对________一组记录进行快速排序。

4.在堆排序,快速排序和归并排序中,若只从存储空间考虑,则应首先选取________方法,其次选取________方法,最后选取________方法:若只从排序结果的稳定性考虑,则应选取________方法:若只从平均情况下排序最快考虑,则应选取________方法:若只从最坏情况下排序最快并且要节省内存考虑,则应选取________方法。

5.在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中,排序是不稳定的有________。

6.在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中,平均比较次数最少的排序是________需要内存容量最多的是________。

7.在堆排序和快速排序中,若原始记录接近正序或反序,则选用________若原始记录无序则最好选用________。

8.在插入和选择排序中,若初始数据基本正序,则选用________若初始数据基本反序,则选用________。

9.对n个元素的序列进行起泡排序时,最少的比较次数是________。 10.两个序列如下：

L1＝{25，57，48，37，92，86，12，33} L2＝{25，37，33，12，48，57，86，92}

用冒泡排序方法分别对序列L1和L2进行排序，交换次序较少的是序列________。 四、算法设计

1.有一种简单的排序算法,叫做计数排序。这种排序算法对一个待排序的表(用数组表示)进行排序,并将排序结果存放到另一个新的表中。必须注意的是,表中所有待排序的关键字互不相同,计数排序算法针对表中的每个记录,扫描待排序的表一趟,统计表中有多少个记录的关键字比该记录的关键字小。假设对某一个记录,统计出数值为c,那么这个记录在新的有序表中的合适的存放位置即为c。 (1)给出适用于计数排序的数据表定义。 (2)编写实现计数排序的算法。

(3)对于有n个记录的表,比较次数是多少?

(4)与直接选择排序相比,这种方法是否更好?为什么? 解: (1) typedef struct {

ElemType data; KeyType key; }listtype;

(2) void countsort(listtype a[],listtype b[],int n) {

int i1,j,count;

for(i1=0;i1

count=0;

19

for(j=0;j

if(a[j].key

(3) 对于有n个记录的表，关键字比较的次数是n2.

(4)直接选择排序比这种计数排序好，因为直接选择排序的比较次数为n*(n-1)/2，且可在原地进行排序（稳定排序），而计数排序为不稳定排序，需要辅助空间多，为O(n).

2.修改冒泡排序法以实现双向冒泡排序。即第一次把最大记录放到表尾，第二次将最小记录放到表头，如此反复进行，直至排序结束。试编写此算法。

第九章 查 找

一、判断题

1.用二分查找法对一个顺序表进行查找，这个顺序表可以是按各键值排好序的，也可以是没有按键值排好序的。（ ）

2.哈希表的查找不用进行关键字的比较。（ ）

3.哈希表的定义函数H（key）=key%p(p<=m)这种方法是直接定址法。（ ） 4.装填因子α的值越大，就越不容易发生冲突。( )

5.选择hash函数的标准为：随机性好、均匀性好和尽量避免冲突。( ) 二、填空题

1.顺序查找法的平均查找长度为________，二分查找法的平均查找长度为________，分块查找法(以顺序查找确定块)的平均查找长度为________，分块查找法(以二分查找确定块〉的平均查找长度为________，哈希表查找法采用链接法处理冲突时的平均查找长度为________。

2.在各种查找方法中,平均查找长度与结点个数n无关的查法方法是________。 3.二分查找的存储结构仅限于________,且是________。

4.在分块查找方法中,首先查找________,然后再查找相应的________。 5.长度为255的表,采用分块查找法,每块的最佳长度是________。 6.在散列函数H(key)=key%p中,p应取________。

7.假设在有序线性表A[1..20]上进行二分查找,则比较一次查找成功的结点数为________,则比较二次查找成功的结点数为________,则比较三次查找成功的结点数为________,则比较四次查找成功的结点数为________,则比较五次查找成功的结点数为________,平均查找长度为________。

8.对于长度为n的线性表,若进行顺序查找,则时间复杂度为________，若采用二分法查找,则时间复杂度为________。

9.己知一个有序表为(12,18,20,25,29,32,40,62,83,90,95,98),当二分查找值为29和90的元素时,分别需要________次和________次比较才能查找成功；若采用顺序查找时,分别需要________次和________次比较才能查找成功。

三、选择题

1.顺序查找法适合于存储结构为（ ）的线性表。 A．散列存储 B．顺序存储或链接存储 C．压缩存储 D．索引存储 2.对线性表进行二分查找时,要求线性表必须（ ）。 A．以顺序方式存储 B．以链接方式存储 C．以顺序方式存储,且结点按关键字有序排序 D．以链接方式存储,且结点按关键字有序排序

3.采用顺序查找方法查找长度为n的线性表时,每个元素的平均查找长度为（ ）。 A．n B．n/2 C．(n+1)/2 D．(n-1)/2 4.采用二分查找方法查找长度为n的线性表时,每个元素的平均查找长度为（ ）。 A．O(n2) B．O(log2n) C．O(n) D．O(log2n)

20

5.二分查找和二叉排序树的时间性能（ ）。 A．相同 B．不相同 C．无法比较

6.有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值为82的结点时,（ ）次比较后查找成功。

A．1 B．2 C．4 D．8 7.设哈希表长m=14,哈希函数H(key)=key。表中已有4个结点: addr(15)=4 addr(38)=5 addr(61)=6

addr(84)=7其余地址为空，如用二次探测再散列处理冲突,关键字为49的结点的地址是（ ）。 A．8 B．3 C．5 D．9

8.有一个长度为12的有序表,按二分查找法对该表进行查找,在表内各元素等概率情况下查找成功所需的平均比较次数为（ ）。

A．35/12 B．37/12 C．39/12 D．43/12

9.采用分块查找时,若线性表中共有625个元素,查找每个元素的概率相同,假设采用顺序查找来确定结点所在的块时,每块应分（ ）个结点最佳。

A．10 B．25 C．6 D．625

10.如果要求一个线性表既能较快地查找,又能适应动态变化的要求,可以采用（ ）查找方法。 A．分块 B．顺序 C．二分 D．散列

11.设有一个长度为100的已排好序的表，用二分查找进行查找，若查找不成功，至少比较（ ）次。

A．9 B．8 C．7 D．6 四、问答题

1.已知一个线性表为(38,25,74,63,52,48),假定采用H(k)=k%7计算散列地址进行散列存储,试分别求出利用线性探测的开放定址法处理冲突和利用链接法处理冲突,在该散列表上进行查找的平均查找长度。

2.己知线性表的元素为(87,25,310,8,27,132,68,95,187,123,70,63,47),散列函数为h(k)=k,采用链接法处理冲突。设计出这种链表结构,并求该表平均查找长度。

3.假定一个待散列存储的线性表为(32,75,63,48，94,25,36,18,70),散列地址空间为[0...10],若采用除留余数法构造散列函数和线性探查法处理冲突,试给出它们对应的散列表,并求出在等概率情况下的平均查找长度。

4.试用连线把右边是四种线性表的存储结构与左边对应的操作的特点连接起来。 (A）散列表 (1）查找和存取速度快,但插入和删除速度慢。 (B)顺序有序表 (2）查找、插入和删除速度快,但不能进行顺序存取。 (C)顺序表 (3）插入、删除和顺序存取速度快,但查找速度慢。 (D)链接表 (4)查找、插入和删除速度慢,但顺序存取和随机存取第i个元素速度快。 五、应用题

设闭散列表容量为7，给定表（30，36，47，52，34），散列函数H（K）＝k mod 6，采用线性探测解决冲突，要求：

（1）构造此散列表(散列地址为0~6)。 （2）求查找34需要进行比较的次数。 六、算法设计 哈希表的删除

hashtable del_hashtable (hashtable &hash, keytype K) {t=h(k);

21

if ( hash[t]= = null) return (\else if (hash[t]= =K) hash[t]=hash[t]->next; else { found=0; q=hash[t];

p=hash[t]->next;

while ((!found)&&(p<> null)) if ( p->key= =K) {found=1;

q->next=p->next; }

else{q=p; p=p->next;}

if(!found) return (\}

return(hash); }

第十章 文 件

1.常见的文件组织方式有哪几种?各有何特点? 文件上的操作有哪几种? 如何评价文件组织的效率?

2.索引文件、散列文件和多关键字文件适合存放在磁带上吗?为什么?

3.设有一个职工文件，其记录格式为(职工号、姓名、性别、职务、年龄、工资)。其中职工号为关键字，并设该文件有如下五个记录：

地址 职工号 姓名 性别 职务 年龄 工资 A 39 张恒珊 男 程序员 25 3270 B 50 王莉 女 分析员 31 5685 C 10 季迎宾 男 程序员 28 3575 D 75 丁达芬 女 操作员 18 1650 E 27 赵军 男 分析员 33 6280 (1)若该记录为顺序文件，请写出文件的存储结构； (2)若该文件为索引顺序文件，请写出索引表；

(3)若该文件为倒排序文件，请写出关于性别的倒排表和关于职务的倒排表。

4.在上题所述的文件中，对下列检索写出检索条件的表达式，并写出结果记录的职工号。 (1)男性职工

(2)工资超过平均工资的职工； (3)职务为程序员和分析员的职工；

(4)年龄超过25岁的男性程序员或分析员； 5.B+树和B-树的主要差异是什么？

6.编写计算二叉树中叶节点个数的递归函数（14分）。

数据结构模拟试题（自测一）

考试时间：2小时

一、单项选择题（每个2分， 共24分）

1.若语句S的执行时间为O（1），那么下列程序段的时间复杂度为（ ）。 for(i=0; i

22

A．O(n) B．O(n*n) C．O(nlogn) D．O(n*i) 2. 已知一堆栈的进栈序列为：1234，则下列哪个序列为不可能的出栈序列（ ）。

A．1234 B．4321 C．2143 D．4123 3. 深度为5的二叉树至多有（ ）个结点.

A．16 B．32 C．31 D．10 4. 堆(HEAP)是一种（ ）。

A．二叉树 B．线性表 C．图 D．算法

5. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？（ ）。

A．1和5 B．2和4 C．4和2 D．5和1 6. 下列哪种排序算法的平均时间复杂度为O（nlogn）（ ）。

A．简单选择排序 B．简单插入排序 C．冒泡排序 D．归并排序

7. 用冒泡排序（交换排序）算法对(12 37 42 19 27 35 56 44 10)数据进行从小到大排序。在将最大的数“沉”到最后时，数据的顺序是（ ）。

A．12 37 42 19 27 35 44 10 56 B．12 37 42 19 27 35 10 44 56 C．12 37 19 27 35 42 44 10 56 D．10 12 19 27 35 37 42 44 56 8. 下列哪种排序算法更适合于外部排序（ ）。

A．选择排序 B．插入排序 C．冒泡排序 D．归并排序 9. 数据结构中的DIJKSTRA方法是用来求（ ）。

A．关键路径 B．最短路径 C．拓扑排序 D．字符串匹配 10. 对下列二叉树进行后序遍历，其遍历结果为（ ）。

a

b c d e f

g

A．gfedcba B．dbegfca C．bdecgfa D．dbaecgf 11.稀疏矩阵（SPARSE MATRIX）一般的压缩存储方法有以下两种（ ）。

A．二维数组和三维数组 B．三元组（TRIPES）和哈希表（HASH TABLE） C．三元组（TRIPES）和十字链表（cross linked） D．哈希表和十字链表 12. 在待排序的元素基本有序的前提下，效率最高的排序方法是（ ）。

A．简单插入排序 B．简单选择排序 C．快速排序 D．归并排序 二、填空题（共16分）

1.、栈和队列都是________线性表。（2分）

2.、下三角形矩阵按行存储的下标计算公式为________(2分)，三对角矩阵按行存储的计算公式为________。（2分）

3.、（4分）在简单插入排序、希尔排序、简单选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有：________。

4.、（2分）请举例输出树形结构的两种存储方法________。

5.、（4分）按满二叉数的概念可推广出满K叉数的概念。若对满K叉树的节点逐层编号（从1开始，同层中从左到右），则编号为i的节点的父节点编号是________，编号为i的节点的第j个儿子的编号是________。 三、应用题（共34分）

1.、请对右图有向图（共10分）：

23

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