2015年珍藏答案

1)填空题：序号1-80

【1，1，2】线性结构中元素之间存在一对一关系，树形结构中元素之间存在 一对多 关系，图形结构中元素之间存在 多对多 关系。

【2，1，2】为了最快地存取数据元素，物理结构宜采用 顺序存储 结构。

【3，1，2】数据结构的三要素是 逻辑结构， 物理结构 ， 操作 。

【4，1，2】数据的逻辑结构可形式地用一个二元组B＝(K，R)来表示，其中K是 数据元素的有限集合__，R是 K上关系的有限集___。

【5，1，2】存储结构可根据数据元素在机器中的位置是否一定连续分为 顺序存储结构__， 链式存储结构___。

【6，1，4】度量算法效率可通过 时间复杂度__来进行。

【7，1，4】算法的五个重要特性是确定性、 可行性 、 有穷性 、输入和输出。

【8，1，4】设n为正整数，则下面程序段的时间复杂度是 O(n)__。

i=1；k=0； while(i

k=k+10*i；i++； }

【9，1，4】设n 为正整数，下面程序段中前置以记号@的语句的频度是 n(n+1)/2 。 for (i=0; i

@ a[i][j]=0; }

【10，1，4】设n 为正整数，试确定下列各程序段中前置以记号@的语句的频度: (1) i=1; k=0;

while (i<=n-1){ i++;

@ k+=10 * i; // 语句的频度是________n-1______________。 } (2) k=0;

for (i=1;i<=n;i++){

for (j=i; j<=n;j++)

@ k++; // 语句的频度是____n(n+1)/2__________________。 }

【11，1，4】按增长率由大到小排列下列函数的结果是__ n2__ n log2 n n _ n1/2__ log2 n ___ log2 (log2 n),______________________。 log2 (log2 n), n log2 n, n2, n1/2, log2 n, n

【12，2，1】当线性表的规模比较大，难以估计其存储规模时，一般以采用 动态链表 的存储结构为好。

【13，2，1】线性表(a1，a2，…，an)有两种存储结构： 顺序存储结构和链式存储结构，请就这两种存储结构完成下列填充：

__顺序_ 存储密度较大；__顺序__存储利用率较高；__顺序__可以随机存取；__链式___不可以随机存取；

__链式__插入和删除操作比较方便。

【14，2，2】从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动 n-i 个元素。

【15，2，3】带头结点的双链表L为空的条件是 L->next=L或L->prior=L 。

【16，2，3】带头结点的单链表Head为空的条件是____ Head->next=NULL ______。

【17，2，3】非空单循环链表L中*p是尾结点的条件是_____p->next=L ___________。

【18，2，3】在一个单链表中p所指结点(p所指不是最后结点)之后插入一个由指针s所指结点，应执行s->next=__ p->next ___;和p->next=___ s_____的操作。

【19，2，3】在一个单链表中的指针p所指结点之前插入一个由指针s所指结点，可执行以下操作序列：

s->next= p->next；____; p->next=s; t=p->data;

p->data=___ s->data;_____; s->data=t;

【20，2，3】在一个单链表中删除p所指结点时，应执行以下操作： q= p->next;

p->data= p->next->data;

p->next= p->next->next _ ; free(q);

【21，2，3】在单链表中，删除指针P所指结点的后继结点的语句是 P->next = P->next->next;___。

【22，2，3】带头结点的单循环链表Head的判空条件是__ Head->next == Head;___； 不带头结点的单循环链表的判空条件是___ Head == NULL; __。

【23，2，3】删除带头结点的单循环链表Head的第一个结点的操作是__ Head->next = Head->next->next; ___；删除不带头结点的单循环链表的第一个结点的操作是__ Head = Head ->next;___。

【24，2，3】已知L是带表头结点的非空单链表, 且P结点既然不首元结点,也不是尾元结点,试从下列提供的答案中选择合适的语句序列。

a. 删除P结点的直接前驱结点的语句序列是______10 12 8 11 4 14 __________________________。

b. 删除结点P的语句序列是_______10 12 7 3 14______________________。 c. 删除尾元结点的语句序列是 9 11 3 14_______________________。 (1) P = P->next; (2) P->next = P;

(3) P->next = P->next ->next; (4) P = P->next ->next;

(5) while (P != NULL) P = P->next;

(6) while (Q->next != NULL){P = Q; Q = Q->next}; (7) while (P->next != Q) P = P->next; (8) while (P->next->next != Q) P = P->next; (9) while (P->next->next != NULL) P = P->next; (10) Q = P;

(11) Q = P->next; (12) P = L;

(13) L = L->next; (14) free (Q);

【25，3，1】栈操作的原则是 先进后出/后进先出 。

【26，3，1】对一个栈，给定输入的顺序是A、B、C，则全部不可能的输出序列有 不可能得到的输出序列有CAB 。

【27，3，1】数据A、B、C、D依次进栈后，再从栈中取一数据，则它是 D。则本栈得到DCBA的输出序列，其理由是 根据后进先出的原则，首先得到D，在栈内的数由底到顶依次是A、B、C，而出栈的次序刚好相反，即DCBA。 。

【28，3，1】.在栈顶指针为HS的链栈中，判定栈空的条件是 head->next==NULL 。

【29，3，1】将递归算法改写成等价的非递归算法，通常应该设置 堆栈 的数据结构

【30，3，2】下列程序把十进制数转换为十六进制数，请填写合适的语句成分。（每空2分）

void conversion10_16() { InitStack(&s); scanf(“%d”,&N); while(N){

① ________Push(s, N)__________ ___ ;

N = N/16; }

while(!StackEmpty(s)){

② _______Pop(s, e)______________ ;

if(e<=9)printf(“%d”,e); else printf(“%c”,e-10+’A’); }

} /* conversion */

【31，3，4】若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素为n，则第i个输出元素是 n－i＋1 。

【32，3，4】若用一个大小为6个元素的数组来实现循环队列，且当前rear=0和front=3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是 2 和 4 。

【33，3，4】已知一个栈的输入序列为1，2，3，…，n,输出序列为a1,a2,a3,…,an，那么a2=n的输出序列共有 n-1 种。

【34，3，4】堆栈和队列都是线性表, 堆栈是_________后进先出___________________________的线性表, 而队列是_______先进先出_____________________________的线性表。

【35，3，4】从循环队列中删除一个元素时，其操作是 先移动队首元素,后取出元素 。

【36，3，4】若用一个大小为6个元素的数组来实现循环队列，且当前rear=0和front=3。

当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是 2 和 4 。

【37，3，4】下面是关于循环队列的操作，请在划线空白处填写合适语句成分。

Status EnQueue(SqQueue &Q, QelemType e) {

if((Q.rear+1)%MAXSIZE==Q.front) ) retrun ERROR;

Q.base[(Q.rear)] = e;

Q.rear=(Q.rear+1)%MAXSIZE ; return OK; } // EnQueue

【38，4，1】空串是 零个字符的串 ，其长度为 零 。

【39，4，1】设串s1=”teachers and “,s2=”students”,则StrLength(s2)= 8 ；Concat(s1,s2)= ”teachers and students” 。

【40，4，1】设s = ‘I AM A TEACHER’，其长度是 14 。

【41，4，1】两个串相等的充分必要条件是 两个串的长度相等且对应位置的字符相同 。

【42，4，2】串的两种最基本的存储方式是 顺序存储方式和链接存储方式 。

【43，4，3】令有串u=”aabcaab”和v=”abcaabcaabcaaba”, (1) 求Index(v,u,5)的值：Index(v,u,5)= 8 ; (2分) (2) 求出u作为模式串时在KMP算法中的next[j]值。(2分) j u next[j]

【44，5，1】二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元，并且A[0][0]的存储地址是200，则A[6][10]的地址是 332。

【45，5，1】设每个元素需要8个字节，顺序存储100个元素,若首地址是2500，那么第50个元素的地址是_____2892________。

【46，5，2】已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A[0][0])，则A[i][j]的地址是 LOC (A[0][0]) + (n*i + j) k

【47，5，2】C语言采用行优先方式存放数组元素，数组下标从0开始。设维数为（5,6,7）的数组A5x6x7的起始存储地址为Loc[0][0][0]=1000，每个数组元素占用4个字节。则元素A[4][4][4]所在的地址Loc[4][4][4]= ___________1800_________________________。

【48，5，2】按行优先次序列出三维数组A[2][3][2]的所有12个元素在内存中的存储次序，它们依次是：

A[0][0][0] A[0][0][1] A[0][1][0] A[0][1][1] A[0][2][0]

1 a 0 2 a 1 3 b 2 4 c 1 5 a 1 6 a 2 7 b 3

A[0][2][1] A[1][0][0] A[1][0][1] A[1][1][0] A[1][1][1] A[1][2][0] A[1][2][1]

【49，5，3】对一个10阶对称矩阵A，采用压缩存储方式（以行序为主序，且A[0][0]的地址为1）,则A[8][5]的地址是 34 。

【50，5，3】对一个10阶三对角矩阵A，采用压缩存储方式（以行序为主序，且A[0][0]的地址为1，每个元素占4个字节）,则A[6][5]的地址是 69 。

【51，5，3】对一个对称矩阵A（aij=aji,0<=i,j<=n），采用下三角压缩存储方式存储在一维数组S[1..M]中（以行序为主序，且A[0][0]=S[1]）,则A[i][j]（i>=j）对应S中的下标是 i*(i+1)/2 + j+1 ；一维数组S的大小M至少为 (n+1)*(n+1) 。

【52，6，1】

已知一棵树边的集合是{,,,,,,,,}。那么根结点是 e ，结点b的双亲是 d ，结点a的子孙有 bcdj ，树的深度是 4 ，树的度是 3 ，结点g在树的第 3 层。

【53，6，2】通常使用 二叉链表 来表示二叉树结构。

【54，6，2】从概念上讲，树与二叉树是二种不同的数据结构，将树转化为二叉树的基本的目的是 .树可采用二叉树的存储结构并利用二叉树的已有算法解决树的有关问题 。

【55，6，2】在图1至图5中, ____1,2,3,4,5____________是树，______1,2,3,4________是二叉树，_____1,2,3_________是完全二叉树，_______1,3__________是满二叉树。

图1 图2 图3 图4 图5

【56，6，3】在图4中，结点H在这棵树的前序、中序和后序遍历次序中分别是___6__、第__5___和第___3___个结点。

i-1h

【57，6，2】满三叉树的第i层的结点个数为 3 ，深度为h时该树中共有 3-1 结点。

【58，6，2】在图4中，A是___根___结点，D是___叶子___结点，B是E的___父亲_____，B是G的____祖先____，D是E的__兄弟______。这棵树的度是___6_____，深度是__4______。

【59，6，2】程序填空：下列算法是求以二叉链表存储的二叉树中的最小值，设数据域的类型为int。

void minnode(BiTree T, int *min) {

if(T!=NULL) {

if( *min>T->data ) *min = T->data; minnode(T->lchild,min);

minnode(T->rchild,min) ; } }

【60，6，2】已知一棵完全二叉树有56个叶子结点，从上到下、从左到右对它的结点进行编号，根结点为1号。则该完全二叉树总共结点有___111_____个；有____7___层；第91号结点的双亲结点是___45____号；第63号结点的左孩子结点是________号。

【61，6，2】下列表示的图中，共有___5____个是树；有___3____个是二叉树；有__2____个是完全二叉树。

【62，6，3】下列二叉树的中序遍历序列是____DBNGOAEC_______;后序遍历序列是_______DNIGBECA_______________________________。

【63，6，3】一棵二叉树的中序遍历序列是DBNGOAEC,后序遍历序列是DNOGBECA，则其先序遍历的序列中的第一个元素是_ A ___，第五个元素是_N _，最后一个元素是_E_

【64，6，3】下列二叉树的先序遍历序列的第5个结点是___N___；第8个结点是__E___；后序遍历序列的第2个结点是_N____；第6个结点是__E___。

【65，6，3】如果某二叉树的后序遍历序列是ABCDEFGHI，中序遍历序列是ACBIDFEHG，则其先序遍历序列的第一个字母是 I ，最后一个字母是 G 。

【66，6，3】程序填空：设算法DFS(Mgraph *G, int i)是无向图G从i顶点开始的深度优先遍历算法。下列算法是判断无向图G是否是连通的。

int isconnect(Mgraph *G) { int i,k=0;

for(i=0; ivexnum; i++) visited[i] = 0;

for(i=0; ivexnum; i++) if(!visited[i])

{ k++ ； DFS(G, i); }

if(k==1) return 1 ； else return 0;

}

【67，7，2】图有 邻接矩阵 和 邻接表 等存储结构。

【68，7，2】设无权图G的邻接矩阵为A，若（vi,vj）属于图G的边集合，则对应元素A[i][j]等于 1 ，设无向图G的邻接矩阵为A，若A[i][j]等于0，则A[j][i]等于 0 。

【69，7，2】若一个图用邻接矩阵表示，则计算第i个结点的入度的方法是 求矩阵第i列非零元素之和 。

【70，7，2】若一个图用邻接矩阵表示，则删除从第i个顶点出发的所有边的方法是 矩阵第i行全部置为零 。

【71，7，4】n个顶点的连通图至少有 n－1 条边。

【72，7，4】设一个图

G={V,{A}},V={a,b,c,d,e,f},A={,,,,,,}。那么顶点e的入度是 2 ；出度是 1 ；通过顶点f的简单回路有 2 条；就连通性而言，该图是 强连通 图；它的强连通分量有 1 个；其生成树可能的最大深度是 5 。

【73，7，5】下面有向图共有____4___个顶点；从v3到v2的最短简单路径之一是___v3—v4—v2______________；v1的出度是___2_____；包含所有顶点的简单路径之一是_______v3—v4—v1—v2______________。

【74，9，2】n个结点的二叉排序树的最大深度是 n ，最小深度为 [log2n]+1

【75， 9，3】设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：

H(key)=key mod 7，表长为10，用开放地址法的二次探测再哈希方法Hi=(H(key)+di) mod 10 (di = 12,22,32,…,)解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。 哈希地址 关键字 比较次数 0 14 1 1 01 1 2 9 1 3 23 2 4 84 3 5 27 4 6 55 1 7 20 2 8 9 平均查找长度：ASL = (1+1+1+2+3+4+1+2)/8 = 15/8 以关键字27为例，H(27)=27%7=8(冲突)，H1=(6+1)=7(冲突)，H2=(6+22)=0(冲突)，H3=(6+33)=5，所以比较了4次。

【76，10，1】排序过程一般需经过两个基本操作，它们是 比较 和 移动 。

【77，10，2】结点的关键字序列是（F,B,J,G,E,A,I,D,C,H），对它按字母的字典序进行排列。如果采用Shell排序方法，那么步长取5时，第一次扫描结果的前5个字母分别是 (A,B,D,C,E) 。

【78，10，2】在对一组关键字是（54,38,96,45,15,72,60,23,83）的记录进行直接插入排序时，当把第七个记录（关键字是60）插入到有序表时，为寻找插入位置需比较 3 次。

【79，10，3】在利用快速排序方法对一组关键字是（54,38,96,45,15,72,60,23,83）的记录进行排序时，需要递归调用partition函数，递归的最大深度（设第一次调用深度为1）为 3 ，共需5次递归调用，其中第二次递归调用是对关键字是 （23，38，15，45） 的一组记录进行的。

【80，10，4】插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序、和基数排序方法中，不稳定的排序方法有 希尔排序、快速排序、堆排序 。

4) 分析计算作图题：序号1-55（选自《数据结构题集》—严蔚敏等编）

【1， 1，4】（选自《数据结构题集》1.8，选做题）

设n为正整数，试确定下列各段程序中前置以记号@的语句的频度(语句的频度指的是该语句重复执行的次数)。

(1) i=1；k=0;

while (i<=n-1){

i++; @ k+=10*i; }

答：该语句的频度为n-1

(2) x=91; y=100; while(y>0){

@ if(x>100) {x-=10; y--;} else x++;

}

答：在循环中，if语句为真1次，else语句执行10次，所以if 语句执行11次y的值减1。该语句的频度为100x(1+10) = 1100

【2， 1，4】（选自《数据结构题集》1.9，选做题）

假设n为2的乘幂，并且n>2，试求下列算法的时间复杂度及变量count的值（以n函数形式表示）

int Time (int n) {

count =0; x=2; while( x

x*=2; count++; }

return (count);

} // Time

答：从while的循环控制可以看出，n每增加一倍,count的值增加1。所以该算法的时间复杂度为O(log2 n)，根据初值，变量count 的值为「log2 (n-2) 」- 1

【3， 2，3】（选自《数据结构题集》2.6，必做题）

已知L是无表头结点的单链表，且P既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。

a．在P结点后插入S结点的语句序列是 ___（4）（1）____ b．在P结点前插入S结点的语句序列是 ___（7）（11）（8）（4）（1）____ c．在表首插入S结点的语句序列是 ____（5）（12）________ d．在表尾插入S结点的语句序列是 ______（9）（1）（6）_______

（1）P —> next ＝ S ；

（2）P —> next ＝ P —> next —> next； （3）P —> next ＝ S —> next； （4）S —> next ＝ P —> next； （5）S —> next ＝ L； （6）S —> next ＝ NULL； （7）Q ＝ P；

（8）while （P —> next ！＝ Q）P ＝ P —> next； （9）while （P —> next ！＝ NULL） P ＝ P —> next； （10）P ＝ Q； （11）P ＝ L； （12）L ＝ S； （13）L ＝ P；

【4， 2，2】（选自《数据结构题集》2.10，选做题）

指出以下算法中的错误和低效（即费时）之处，并将它改写为一个既正确又高效的算法。

Status DeleteK（SqList &a，int i，int k）{

//本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素

if（i < 1 || k < 0 || i + k > a.length）return INFEASIBLE；// 参数不合法 else {

for（count ＝ 1；count < k；count ++）{ //删除一个元素

for（j ＝ a.length；j >＝ i +1；j ――）a.elem[j－1] ＝ a.elem[j]；

a. length ――；

} return OK； } // DeleteK

答：错误之处：题中有下划线处应改为：

for （j ＝ i+1；j <= a.length；j++） a.elem[j－1] ＝ a.elem[j]；

低效费时之处：该算法每删除一个元素，其后所有的元素都向前移一位，包括将要删除的元素，比较耗时间。（其中n＝a.length） 下划线的语句的频度为：

改进方法是将k个元素在一个循环内删除，算法如下： Status DeleteK（SqList &a，int i，int k）{

//本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素

if（i < 1 || k < 0 || i + k > a.length）return INFEASIBLE；// 参数不合法

else {

for（count ＝ 0；count < a.length－k－i；count ++）

a.elem[i-1+ count] ＝ a.elem[k + i-1 + count ]；

//删除k个元素

a.length ＝ a.length－k；

}

return OK； } // DeleteK

【5， 3，1】（选自《数据结构题集》3.4，必做题）

简述以下算法的功能（栈的元素类型 SElemType为int）

（1）Status algo1（Stack S）{ int i，n，A[255]； n ＝ 0；

while （！StackEmpty（S）） {n ++；Pop（S，A[n]）；} for（i ＝ 1；i <＝ n；i ++）Push（S，A[i]）； }

功能：利用数组A，将栈中所有的元素倒置。

（2）Status algo2（Stack S，int e）{ Stack T；int d； InitStack（T）；

while（！StackEmpty（S））{ Pop（S，d）；

if（d！＝e）Push（T，d）； }

while（！StackEmpty（T））{ Pop（T，d）； Push（S，d）； } }

功能：将栈S中与e相同的元素删除。

【6， 3，1】（选自《数据结构题集》3.15，选做题）

假设以顺序存储结构实现一个双向栈，即在一堆数组的存储空间中存在着两个栈，它们的栈底分别设在数组的两个端点。试编写实现这个双向栈tws的三个操作：初始化inistack（tws）、入栈push（tws，i，x）和出栈pop（tws，i）的算法，其中i为0或1，用以分别指示设在数组两端的两个栈，并讨论按过程（正/误状态变量可设为变参）或函数设计这些操作算法各有什么优缺点。

typedef struct {

SElemType *base[2]; SElemType *top[2]; int stacksize; } SqStack;

Status initstack ( SqStack &tws) { // 初始化，构造一个空栈tws

tws．base[0] ＝（SElemType *）malloc（STACK_INIT_SIZE * sizeof（））； if（！tws.base[0]）exit（OVERFLOW）； // 存储分配失败 tws．stacksize ＝ STACK_INIT_SIZE；

tws．base[1] ＝ tws．base[0] + tws.stacksize－1;

tws．top[0] ＝ tws．base[0];

tws．top[1] ＝ tws．base[1]; return OK； } // initstack

Status push（SqStack &tws，int i，ElemType x） { // 插入元素x为新的栈顶元素

if（tws.top[0] － base[0] + tws.top[1] － base[1] >= tws.stacksize） { // 栈满，追加存储空间

increment0 = tws.top[0] － base[0]; //０端的元素个数 increment1 = tws.top[1] － base[1]; //１端的元素个数

tws．base[0] ＝（SElemType *）realloc（tws.base[0] ,(tws.base[0]+

STACKINCREMENT) * sizeof（ElemType））； if（！tws.base[0]）exit（OVERFLOW）； // 存储分配失败 tws.stzcksize += STACKINCREMENT; temp=tws.base[1];

tws．base[1] ＝ tws．base[0] + tws.stacksize－1; for(i=0; i

if（i） * tws.top[1] -- = x； else

* tws.top[0] ++ = x； return OK;

} // push

Status pop（SqStack &tws，int i） {

// 若栈不空，则删除tws的栈顶元素，并返回OK；否则返回ERROR if（tws.top[0] ＝＝ base[0] || tws.top[1] ＝＝ base[1]） return ERROR； if（i） ++ tws.top[1]； else

――tws.top[0]；

return OK； } // pop

【7， 3，4】（选自《数据结构题集》3.13，必做题）

简述以下算法的功能（栈和队列的元素类型均为int）

void algo3(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); } }

答：将队列Q中的元素变成倒置排列。

【8， 3，2】（选自《数据结构题集》3.19，选做题）

假设一个算术表达式中可以包含三种括号：圆括号“（”和“）”，方括号“[”和“]”和花括号“{”和“}”，且这三种括号可以按任意的次序嵌套使用（如：?[?{?}?[?]?]?[?]?(?)?）。编写判别给定表达式所含括号是否正确配对出现的算法（已知表达式已存入数据元素为字符的顺序表中）。

解：算法如下：

Status MatchBrackets ( ) { SqStack &S; InitStack (S);

while ((c=getchar())!=‘\\n’){

if(!StackEmpty (S) && (c==‘)’&& GetTop (S)==‘(’||

c==‘ ]’ && GetTop (S)== ‘[’||

c==‘}’ && GetTop (S)==‘{’) )

Pop (S); //判断括号是否匹配

else

if(IsLeftBracket(c)) Push (S, c)； //判断是否是括号

}

if(!StackEmpty(S)) return ERROR; else return TRUE; }

【9， 4，1】（选自《数据结构题集》4.3，必做题）

设s =‘I AM A STUDENT’,t =‘GOOD’,q =‘WORKER’。求：

StrLength(s), StrLength(t), SubString(s,8,7), SubString(t,2,1), Index(s, ‘A’), Index(s, t), Replace(s, ‘STUDENT’,q ), Concat(SubString(s,6,2),Concat(t,SubString(s,7,8))) 答：StrLength(s) = 14, StrLength(t) = 4,

SubString(s,8,7) =‘STUDENT’, SubString(t,2,1) =‘O’, Index(s,‘A’) = 3, Index(s, t) = 0,

Replace(s, ‘STUDENT’,q ) = ‘I AM A WORKER’,

Concat(SubString(s,6,2),Concat(t,SubString(s,7,8))) =‘A GOOD STUDENT’

【10， 5，1】（选自《数据结构题集》5.1，必做题）

假设有两维数组A6x8，每个元素用相邻的6个字节存储，存储按字节编址。已知A的起始地址为1000，计算：

(1) 数组A的存储量； = 6x8x6 = 288 (字节)

(2) 数组A的最后一个元素a57的第一个字节的地址；=1000+288-6=1282

(3) 按行存储时，元素a14的第一个字节的地址；=1000+(8x1+4)x6=1072 (4) 按列存储时，元素a47的第一个字节的地址；=1000+(7x6+4)x6=1276

【11， 6，1】（选自《数据结构题集》6.1，必做题）

已知一棵树边的集合为{，，，，，，，，，，，，}，请画出这棵树，并回答下列问题： （1）哪个是根结点？ （2）哪些是叶子结点？

（3）哪个是结点G的双亲？ （4）哪些是结点G的祖先？ （5）哪些是结点G的孩子？ （6）哪些是结点E的子孙？

（7）哪些是结点E的兄弟？哪些是结点F的兄弟？ （8）结点B和N的层次号分别是什么？ （9）树的深度是多少？

（10）以结点C为根的子树的深度是多少？ 解：这棵树为:

所以，根结点为A；

叶子结点是D，M，N，F，J，K，L； 结点G双亲为C；

结点G的祖先为A，C； 结点E的子孙为I，M.，N；

结点E的兄弟有D，结点F的兄弟有G，H； 结点B和N的层次号分别是2，5； 树的深度是5；

以结点C为根的子树的深度为3。

【12， 6，1】（选自《数据结构题集》6.4，选做题）

一棵深度为H的满k叉树有如下性质第H层上的结点都是叶子节点，其余各层上每个结点都有k棵非空子树。如果按层次顺序从1开始对全部结点编号，问： （1）各层的结点数目是多少？

（2）编号为p的父结点（若存在）的编号是多少？

（3）编号为p的结点的第i个儿子结点（若存在）的编号是多少？

（4）编号为p的结点有右兄弟的条件是什么？其右兄弟的编号是多少？ 解：（1）各层的结点数为

（n＝1，2，…，H）；

时，通过归纳可得，编号为a的结到

，则编号为p的结点的父

（2）首先，p＝1时，没有父结点，点，它的所有子结点的编号为从

结点为「；

（3）由上可得，第i个儿子结点的编号为；

（4）p有右兄弟，即p不为最右的结点，条件为编号为p＋1。

，右兄弟的

【13， 6，2】（选自《数据结构题集》6.5，选做题）

已知一棵度为k的树中有个度为1 的结点，个度为2 的结点，…，个度为k的结点，问该树中有多少个叶子结点？ 解：设结点总数为n，则有n= n0+n1+n2+…+nk，

因为除了根结点外，所有结点都有边进入，所以有n=B+1,而 B = 1*n1+2*n2+…+k*nk = ∑i*ni ,所以有 n0+n1+n2+…+nk = ∑i*ni + 1 n0 = ∑（i-1）*ni + 1

【14， 6，3】（选自《数据结构题集》6.13，必做题）

假设n和m为二叉树中的两结点，用“1”、“0”、“Φ”（分别表示肯定、恰恰相反或者不一定）填写下表： 已知 \\ 问 前序遍历时 中序遍历时 后序遍历时 答: n在m前？ n在m前？ n在m前？ 1 1 1 n在m左方 0 0 0 n在m右方 1 0 Φ n是m祖先 0 1 Φ n是m子孙 注：如果（1）离a和b最近的共同祖先p存在，且（2）a在p的左子树中，b在p的右子树中，则称a在b的左方（即b在a的右方）

【15， 6，3】（选自《数据结构题集》6.14，选做题）

找出所有满足下列条件的二叉树：

（a）它们在先序遍历和中序遍历时，得到的结点访问序列相同； （b）它们在后序遍历和中序遍历时，得到的结点访问序列相同； （c）它们在先序遍历和后序遍历时，得到的结点访问序列相同； 答：（a）除叶子结点外所有结点都只有右孩子的树或只有根结点的树； （b）只有根结点以及除叶子结点外所有结点都只有左孩子的树； （c）只有根结点的树。

【16， 6，4】（选自《数据结构题集》6.19，必做题）

分别画出和下列树对应的各二叉树：

答：用孩子兄弟表示法将树表示成二叉树，二叉树的左右结点分别为第一个孩子结点和下一个兄弟结点，表示如下：

【17， 6，3】（选自《数据结构题集》6.23，选做题）

画出和下列已知序列对应的树T

树的先根次序访问序列为GFKDAIEBCHJ； 树的后根次序访问序列为DIAEKFCJHBG。 解：对应的树如下：

【18， 6，5】（选自《数据结构题集》6.26，必做题）

假设用于通信的电文仅有8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10.试为这8个字母设计哈夫曼编码。使用0－7的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。

解：哈夫曼编码树如下：

所以编码如下： 0.07 0.19 0.02 0.06 0.32 0.03 0.21 0.10 字母 1010 00 10000 1001 11 10001 01 1011 编码 带权路径长度WPL＝0.19×2＋0.21×2＋0.02×5＋0.03×5＋0.06×4＋0.07×4＋0.10×4＋0.32×2＝2.61，而采用等长编码时，每个字母至少3位，故带权路径长度WPL＝3.采用哈夫曼编码可以大大提高通信信道的利用率。

【19， 6，2】（选自《数据结构题集》6.29，必做题）

假设一棵二叉树的层序序列为ABCDEFGHIJ和中序序列为DBGEHJACIF。请画出该树。

解：该二叉树如下：

【20， 7，2】（选自《数据结构题集》7.1，必做题）

已知如右图所示的有向图，请给出该图的

（1） 每个顶点的入/出度； （2） 邻接矩阵； （3） 邻接表； （4） 逆邻接表； （5） 强连通分量。

答：（1）各顶点的入/出度如下：

顶点1：3/0；顶点2：2/2；顶点3：1/2；顶点4： 1/2； 顶点5：2/1；顶点6：2/3。 （2）邻接矩阵如下： 1 2 3 4 1 0 0 0 0 2 1 0 0 1 3 0 1 0 0 4 0 0 1 0 5 1 0 0 0 6 1 1 0 0 （3）邻接表如下： 5 0 0 0 1 0 1 6 0 0 1 1 0 0

（4） 逆邻接表如下：

（5） 有以下3个强连通分量

【21， 7，3】（选自《数据结构题集》7.4，选做题）

试对教科书7.1节中图7.3（a）所示的无向图 (如下图)，画出其广度优先生成森林。

答：其广义优先生成森林如下：

【22， 7，4】（选自《数据结构题集》7.5，选做题）

已知以二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。

1 2 3 4 5 6 7 8 9 10

1 0 0 0 0 0 1 0 1 0 1

2 0 0 0 0 0 1 0 0 0 0

3 0 1 0 0 0 0 1 0 0 0

4 0 0 1 0 0 0 0 1 0 0

5 0 0 0 1 0 0 0 0 1 0

6 0 0 0 0 1 0 0 0 0 1

7 1 1 0 0 0 0 0 0 1 0

8 0 0 1 0 0 0 0 0 0 0

9 1 0 0 1 0 0 0 1 0 0

10 0 0 0 0 1 0 1 0 1 0

答：其深度优先生成树和广度优先生成树分别如下：

【23， 7，4】（选自《数据结构题集》7.7，必做题） 请对下图的无向带权图，

（1） 写出它的邻接矩阵，并按普里姆算法求其最小生成树； （2） 写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。

答：(1) 其邻接矩阵为

a b c d e f g h

a 0 4 3 0 0 0 0 0

b 4 0 5 5 9 0 0 0

c 3 5 0 5 0 0 0 5

d 0 5 5 0 7 6 5 4

e 0 9 0 7 0 3 0 0

f 0 0 0 6 3 0 2 0

g 0 0 0 5 0 2 0 6

h 0 0 5 4 0 0 6 0

按普里姆算法，得最小生成树为

(2) 其邻接表为：

按克鲁斯卡尔算法求得的最小生成树同上。

【24， 7，5】（选自《数据结构题集》7.10，选做题）

对于题7.10图所示的AOE网络，计算各活动弧的e（ai）和l（aj）函数值、各事件（顶点）的ve（vi）和vl（vj）函数值；列出各条关键路径

解：e（ai）为活动ai的最早开始时间，l（aj）为活动aj最迟必须开始的时间，ve（ai）为事件的最早发生时间，vl（aj）为事件的最迟发生时间 活动 （α，A） （α，B） （α，D） （α，F） （α，G） （α，I） （A，C） （B，C） （D，C） （D，E） （D，J） （F，E） 事件 α A B C D E ve（ai） 0 1 6 11 3 34 vl（aj） 0 20 24 26 19 34 事件 G H I J K ω ve（ai） 3 13 1 31 22 44 vl（aj） 3 13 7 31 22 44 e（ai） 0 0 0 0 0 0 1 6 3 3 3 4 L（aj） 19 18 16 4 0 6 20 24 19 26 25 23 L-e 19 18 16 4 0 6 19 18 16 23 22 19 活动 （F，H） （G，ω） （G，H） （I，H） （C，E） （H，C） （H，J） （H，K） （K，J） （J，E） （J，ω） （E，ω） e（ai） 4 3 3 1 17 13 13 13 22 31 31 34 L（aj） 8 23 3 7 26 22 27 13 22 31 32 34 L-e 4 20 0 6 26 9 14 0 0 0 1 0 F

4 8 关键路经：α—G—H—K—J—E—ω

【25， 7，6】（选自《数据结构题集》7.11，必做题）

试利用Dijkstra算法求题7.11图中从顶点a到其他各顶点间的最短路径，写出执行算法中各步的状态。

解： 终点 Dist K＝1 K＝2 K＝3 K＝4 K＝5 K＝6 b 15 (a,b) 15 (a,b) 15 (a,b) 15 (a,b) 15 (a,b) 15 (a,b) c 2 (a,c) d 12 (a,d) 12 (a,d) 11 (a,c,f,d) 11 (a,c,f,d) e 10 (a,c,e) 10 (a,c,e) f 6 (a,c,f) g 16 (a,c,f,g) 16 (a,c,f,g) S {a,c} {a,c,f} {a,c,f,e} {a,c,f,e,d} 14 {a,c,f,e,d,g} (a,c,f,d,g) {a,c,f,e,d,b}

【26， 9，1】（选自《数据结构题集》9.3，必做题）

画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。 解：其判定树如下：

所以，平均查找长度ASL＝1×0.1＋2×0.2＋3×0.4＋4×0.3＝2.9

【27， 9，2】（选自《数据结构题集》9.10，选做题）

可以生成如下二叉排序树的关键字的初始排列有几种？请写出其中的任意5个。

解：30种。任写5个序列如下： （5，4，7，6，2，3，1）； （5，7，4，6，2，3，1）； （5，4，7，2，3，1，6）； （5，7，6，4，2，3，1）； （5，7，6，4，2，1，3）

【28， 5，1】（选自《数据结构题集》9.21，选做题） 在地址空间为0～16的散列区中，对以下关键字序列构造两个哈希表：（Jan，Feb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec） （1）用线性探测开放定址法处理冲突； （2）用链地址法处理。

并分别求这两个哈希表在等概率情况下查找成功和不成功时的平均查找长度。 设哈希函数为H（x）＝「i/2」，其中i为关键字第一个字母在字母表中的序号。 解：（1）用线性探测开放定址法处理冲突

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Apr Aug Dec Feb Jan Mar May June July Sep Oct Nov ASLsucc＝（1×5＋2×3＋4＋5×2＋6）/12=31/12 ASLunsucc＝(5×6/2+9×10/2)/14 = 60/14 （2）用链地址法处理

ASLsucc＝（1×7＋2×4＋3）/ 14 = 18 / 12

ASLunsucc＝（1×7＋2×3＋3×3＋4）/ 14 = 26 / 14

【29， 10，4】（选自《数据结构题集》10.1，必做题）

以关键码序列（503，087，512，061，908，170，897，275，653，426）为例，手工执行以下排序算法，写出每一趟排序结束时的关键码状态： （1）直接插入排序；（3）快速排序；（4）堆排序 答：（1）直接插入排序 （503），087，512，061，908，170，897，275，653，426 （087，053），512，061，908，170，897，275，653，426 （087，503，512），061，908，170，897，275，653，426 （061，087，503，512），908，170，897，275，653，426 （061，087，503，512，908），170，897，275，653，426 （061，087，170，503，512，908），897，275，653，426 （061，087，170，503，512，897，908），275，653，426 （061，087，170，275，503，512，897，908），653，426 （061，087，170，275，503，512，653，897，908），426 （061，087，170，275，426，503，512，653，897，908） （3）快速排序

初 始：503，087，512，061，908，170，897，275，653，426 第一趟：426，087，275，061，170，503，897，908，653，512 第二趟：170，087，275，061，426，503，512，653，897，908 第三趟：061，087，170，275，426，503，512，653，897，908 第四趟：061，087，170，275，426，503，512，653，897，908 第五趟：061，087，170，275，426，503，512，653，897，908 （4）堆排序 初 始：（503，087，512，061，908，170，897，275，653，426） 初始堆：（908，653，897，503，426，170，512， 275，061，087） 第一趟：（897，653，512，503，426，170，087， 275，061），908 第二趟：（653，503，512，275，426，170，087， 061），897，908 第三趟：（512，503，170，275，426，061，087），653，897，908 第四趟：（503，426，170，275，087，061），512，653，897，908 第五趟：（426，275，170，061，087），503，512，653，897，908 第六趟：（275，087，170，061），426，503，512，653，897，908 第七趟：（170，087，061），275，426，503，512，653，897，908 第八趟：（087，061），170，275，426，503，512，653，897，908 第九趟：（061），087，170，275，426，503，512，653，897，908

【30， 10，4】（选自《数据结构题集》10.12，必做题） 判别以下序列是否为堆（小顶堆或大顶堆）。如果不是则把它调整为堆。（要求记录交换次数最少）

（1）（100，86，48，73，35，39，42，57，66，21）； （2）（12，70，33，65，24，56，48，92，86，33）； （3）（103，97，56，38，66，23，42，12，30，52，06，20）； （4）（05，56，20，23，40，38，29，61，35，76，28，100）。

解：（1）大顶堆；

（2）否。调整为小顶堆如下：

（12，24，33，65，33，56，48，92，86，70）

（3）大顶堆；

（4）否。调整为小顶堆如下：

（05，23，20，35，28，38，29，61，56，76，40，100）

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