假设用带头结点的单循环链表表示线性表，单链表的类型定义如下：typedef struct node {int data;struct node*next;}LinkNode，*LinkList;编写程序，求头指针为head的单循环链表中da

答案是：教师释疑： return|0

已知二叉树的定义如下：typedef struct node{int data;struct node *lchild, *rchild;}*Bitptr；编写递归算法求二叉树的高度。函数原型为：int f34（Bitptr

答案是：教师释疑： !t|f34(t->lchild)|f34(r->child)

已知二叉树采用二叉链表存储，其结点结构定义如下： typedef struct Node{ ElmType data； struct Node *lchild，*rchild； }*BiTree； 请编写递归函数

答案是：教师释疑： T->lchild==null|T->rchild==null

二叉排序树的类型定义如下：typedef struct BSTNode {∥ 二叉排序树的结点结构int data; ∥数据域struct BSTNode *lchild, *rchild; ∥左、右孩子指针}BSTNode

答案是：教师释疑： T->lchild|T->rchild

假设线性表采用顺序存储结构，其类型定义如下：#define ListSize 100typedef struct {int data［ListSize］;int length;} SeqList, *Table;编写算法，将

答案是：教师释疑： L->length

若需高效地查询多关键字文件，可以采用的文件组织方式为___________。

答案是：教师释疑： 倒排文件

如果要为文件中的每个记录建立一个索引项，则这样建立的索引表称为___________。

答案是：教师释疑： 稠密索引

ISAM文件系统中采用多级索引的目的是___________。

答案是：教师释疑： 提高检索效率

不定长文件指的是文件的____________大小不固定。

答案是：教师释疑： 记录

已知一组待排记录的关键字序列为(16，12，18，60，15，36，14，18，25，85)，用堆排序方法建小根堆，请给出初始建堆后的序列12,15,14, ,16,36,18,60,25,85 。

答案是：教师释疑： 18

不稳定的排序算法有选择排序、 、希尔排序、堆排序，稳定的排序算法有冒泡排序、 、归并排序和基数排序是稳定的排序算法。

答案是：教师释疑： 快速排序，插入排序

下面程序实现插入排序算法。 typedef struct{ int key; Info otherinfo; }SeqList; void InsertSort(SeqList R［］,int n)

答案是：教师释疑： (1)x=R[i](2)R[mi].key=x.key(3)R[i-j]=R[i-j-1]

已知一组待排记录的关键字序列为(16，12，18，60，15，36，14，18，25，85)，用堆排序方法建小根堆，请给出初始建堆后的序列。

答案是：教师释疑： 12，15，14，18，16，36，18，60，25，85

已知待排记录的关键字序列为{25，96，11，63，57，78，44}，请回答下列问题： (1)画出堆排序的初始堆（大根堆）； (2)画出第二次重建堆之后的堆。

答案是：教师释疑： (1){96,63,78,25,57,11,44} (也可以画出对应的堆形式)(2){63,57,44,25,11,78,96}(也可以画出对应的堆形式)

对关键字序列(72，87，61，23，94，16，05，58)进行堆排序，使之按关键字递减次序排列。请写出排序过程中得到的初始堆和前三趟的序列状态。

答案是：教师释疑： 初始堆：(05,23,16,58,94,72,61,87)第1趟：(16,23,61,58,94,72,87,05)第2趟：(23,58,61,87,94,72,16,05)第3趟：(58,72,61,87,94,23,16,05)

在关键字序列(07，12，15，18，27，32，41，92)中用二分查找法查找和给定值92相等的关键字，请写出查找过程中依次和给定值“92”比较的关键字为18，_____，41，92。

答案是：教师释疑： 32

下面程序实现二分查找算法。 Typedef struct{ KeyType key； InfoType otherinfo； }SeqList[N+1]； int BinSearch(SeqL

答案是：教师释疑： (1)low<=high (2)R[mid].key==K (3)low=mid+1

已知关键字序列为(56，23，41，79，38，62，18)，用散列函数H(key)=key%11将其散列到散列表HT[0..10]中，采用线性探测法处理冲突。请回答下列问题： (1)画出散列存储后的散列表： (2)求在等概率情况下查找

答案是：教师释疑： (1)(2)11/7

若无向图G中有n个顶点m条边，采用邻接矩阵存储，则该矩阵中非0元素的个数为__;

答案是：教师释疑： 2m

若采用邻接矩阵结构存储具有n个顶点的图，则对该图进行广度优先遍历的算法时间复杂度为________。n个顶点且含有环路的无向连通图中，至少含有_______ 条边。

答案是：教师释疑： O(n*n)，n

在有向图中，以顶点v为终点的边的数目称为v的__;含n个顶点的无向连通图中至少含有___条边。

答案是：教师释疑： 入度，n-1

求最小生成树的克鲁斯卡尔(Kruskal)算法耗用的时间与图中____的数目正相关；一个有n个顶点的无向连通图，最少有____条边;

答案是：教师释疑： 边;n-1

若用邻接矩阵表示有向图，则顶点i的入度等于矩阵中_____。

答案是：教师释疑： 第i列非∞元素个数

若采用邻接矩阵结构存储具有n个顶点的图，则对该图进行广度优先遍历的算法时间复杂度为__;n个顶点且含有环路的无向连通图中，至少含有__条边;

答案是：教师释疑： O(n*n);n

已知有向图G的定义如下： G=(V，E) V={a，b，c，d，e} E={， ，，，，，} (1)画出G的图形； (2)

答案是：教师释疑： (1)(2)abecd;aebcd;eabcd

由森林转换得到的对应二叉树如图所示，写出原森林中第三棵树的前序序列和后序序列 A / \ /

答案是：教师释疑： 前序序列：GHIJ后序序列：HJIG

请根据下面哈夫曼树进行译码，写出原来的电文 由字符集{s,t,a,e,l}及其在电文中出现的频度构建的哈夫曼树如图所示，已知某段电文的哈夫曼编码为111000010100，请根据该哈夫曼树进行译码，写出原来的电文。

答案是：教师释疑： eatst

假设二叉树的RNL遍历算法定义如下：若二叉树非空，则依次执行如下操作: （1）遍历右子树 （2）访问根节点； （3）遍历左子树 已知一棵二叉树如图所示，请给出其RNL遍历的结果序列。 A

答案是：教师释疑： GCFABD

已知一棵完全二叉树中共有768结点，则该树中共有 _____个叶子结点。

答案是：教师释疑： 384

假设用表示树的边（其中x是y的双亲），已知一棵树的边集为{,,,,,}，该树的度是_____ 。

答案是：教师释疑： 3

在n个结点的线索二叉链表中，有___个线索指针;已知完全二叉树T的第5层只有7个结点，则该树共有___个叶子结点;

答案是：教师释疑： n+1,11

二叉树的四种遍历方法有___、___、___和___。

答案是：教师释疑： 中序遍历、先序遍历、后序遍历、层次遍历

假设一棵完全二叉树含1000个结点,则其中度为2的结点数为___;在含有3个结点a，b，c的二叉树中，前序序列为abc且后序序列为cba的二叉树有___棵;

答案是：教师释疑： 499,2

假设通信电文使用的字符集为{a,b,c,d,e,f,g}，字符的哈夫曼编码依次为：0110，10，110，111，00，0111和010。 (1)请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应字符； (2)若这些字符在电文中出现

答案是：教师释疑： 253

假设以有序对表示从双亲结点到孩子结点的一条边，若已知树中边的集合为{,,,,,,,,,},请回答下列问题： （1）哪个结点是根结点？ （

答案是：教师释疑： （1）a（2）b,d,f,h,i,j,k（3）a,c,g（4）i（5）4

广义表L=（a，（b，( )））的深度为__。广义表G=(a,b，(c，d，(e，f))，G)的长度为__。

答案是：教师释疑： 3，4

广义表的“深度”是指一个广义表的“深度”是指表展开后所含括号的 ___________。

答案是：教师释疑： 层数

广义表和线性表的区别与联系是：广义表是 的推广；线性表的元素仅限于原子项，若允许其元素具有自身结构，即构成广义表。

答案是：教师释疑： 线性表

已知广义表如下：A=(B,y) B=(x，L) L=(a，b) 要求：写出下列操作的结果 tail(A)=__. head(B)=__。

答案是：教师释疑： (y),x

假设一个10阶的下三角矩阵A按列优顺序压缩存储在一维数组C中，则C数组的大小应为___。假设以列优先顺序存储二维数组A[5][8]，其中元素A[0][0]的存储地址为LOC（a00）,且每个元素占4个存储单元，则数组元素A[i][j]的存储

答案是：教师释疑： 55，LOC(a00)+4*(5*j+i)

假设一个6阶的下三角矩阵B按列优先顺序压缩存储在一维数组A中，其中A［0］存储矩阵的第一个元素b11,则A［14］存储的元素是________。

答案是：教师释疑： b63

假设以列优先顺序存储二维数组A[5][8]，其中元素A[0][0]的存储地址为LOC（a00）,且每个元素占4个存储单元，则数组元素A[i][j]的存储地址为___________。

答案是：教师释疑： LOC(a00)+4*(5*j+i)

设二维数组A5X6的每个元素占4个字节，已知LOC（a00）=1000，A共占________个字节？A的终端结点a45的起始地址为__________？按行和按列优先存储时，a25的起始地址分别为___________和_________

答案是：教师释疑： 120，1116，1068，1108

阅读下列算法，并回答问题： (1)假设数组L［8］={3,0,5,1,6,4,2,7}，写出执行函数调用f32(L，8)后的L； (2)写出上述函数调用过程中进行元素交换操作的总次数。 void f32(int R［］,int n

答案是：教师释疑： (1)L[8]={0,1,2,3,4,5,6,7}(2)共进行5次元素交换

已知稀疏矩阵采用带行表的三元组表表示，其形式说明如下： #define MaxRow 100 //稀疏矩阵的最大行数 typedef struct { int i,j,v; //行号、列号、元素值

答案是：教师释疑： ①it②&R->data[i].i③&R->data[i].j④k++

特殊矩阵和稀疏矩阵哪一种采用压缩存储会失去随机存取的功能？为什么？

答案是：教师释疑： 因稀疏矩阵的非0元素的分布是没有规律的，其压缩存储是采用三元组表方式。所以稀疏矩阵压缩后会失去随机存取的功能。

字符串“sgabacbadfgbacst” 中存在有 ____个与字符串“ba”相同的子串。在串S=“structure”中，以t为首字符的子串有 ________个。

答案是：教师释疑： 3,12

在串匹配中，一般将主串称为目标串，将子串称为_______。链串的结点大小定义为结点的_________中存放的字符个数。

答案是：教师释疑： 模式串，数据元素

已知substr(s,i,len)函数的功能是返回串s中第i个字符开始长度为len的子串，strlen(s)函数的功能是返回串s的长度。若s=″ABCDEFGHIJK″,t=″ABCD″,执行运算substr(s,strlen(t), st

答案是：教师释疑： “EFGH”

串是一种特殊的线性表，其特殊性体现在它的数据元素是 ，另外串的基本操作和线性表有很多的区别，在串的基本操作中，通常以“ ”作为操作对象。

答案是：教师释疑： 字符，串的整体

空格串是指 空格字符(ASCII码为20H)组成的串，而空串是 任何字符的串，其长度为0。

答案是：教师释疑： 一个或多个，不含

阅读下列程序，并回答问题： #include substr(char*t,char*s,int pos,int len) { while（len>0&&*s） { *t=*(s+pos-l);

答案是：教师释疑： (1)"gnirtS" (2)将字符串s中的字符倒置。

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

答案是：教师释疑： 4

算法f31的功能是清空带头结点的链队列Q。请在空缺处填入合适的内容，使其成为一个完整的算法。 typedef struct node{ DataType data； struct node *next； }Qu

答案是：教师释疑： (1)Q->front->next(2)Q->front->next(3)Q->front

阅读下列算法，并回答问题： （1）Q、Q1和Q2都是队列结构，设队列Q=（1，0，-5，2，-4，-6，9），其中1为队头元素，写出执行f31 (&Q,&Q1,&Q2)之后队列Q、Q1和Q2的状态； （2）简述算法f31的功能。

答案是：教师释疑： (1)Q=() Q1=(1,0,2,9) Q2=(-5,-4,-6) (2)将队列Q的元素依次出队，并将正值元素及0元素入队到Q1，负值元素入队到Q2

假设以数组seqn［m］存放循环队列的元素，设变量rear和quelen分别指示循环队列中队尾元素的位置和元素的个数。 (1)写出队满的条件表达式； (2)写出队空的条件表达式； (3)设m=40,rear=13,quelen=19,

答案是：教师释疑： (1)quelen==m(2)quelen==0(3)35(4)(rear-quelen+1+m)%m

简述队列和栈这两种数据类型的相同点和差异点。

答案是：教师释疑： 栈和队列都是一种运算受限的线性表；栈其限制是仅允许在表的一端进行插入和删除运算，队列其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。

若进栈序列为a，b，c，且进栈和出栈可以穿插进行，则可能出现____个不同的出栈序列。

答案是：教师释疑： 3

假设为循环队列分配的向量空间为Q[20]，若队列的长度和队头指针值分别为13和17，则当前尾指针的值为______。

答案是：教师释疑： 10

已知循环队列的存储空间大小为m，队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置，则在队列不满的情况下，队列的长度是___。

答案是：教师释疑： (rear-front+m)%m

栈下溢是指在____时进行出栈操作。

答案是：教师释疑： 栈空

栈顶的位置是随着______ 操作而变化的。设栈S的初始状态为空，若元素a、b、c、d、e、f依次进栈，得到的出栈序列是b、d、c、f、e、a，则栈S的容量至少是___。

答案是：教师释疑： 进栈和退栈，3

假设循环队列的元素存储空间大小为m，队头指针f指向队头元素，队尾指针r指向队尾元素的下一个位置，则在少用一个元素空间的前提下，表示“队满”的条件是___。

答案是：教师释疑： f==(r+1)%m

栈和线性表的差别为线性表是具有 的数据元素的一个有限序列。栈是限定仅在 进行插入或删除操作的线性表。

答案是：教师释疑： 相同特性，表尾

设栈S=(1,2,3,4,5,6,7),其中7为栈顶元素。请写出调用algo(&s)后栈S的状态。 void algo(Stack *S) { int i=0; Queue Q; Stack T;

答案是：教师释疑： s=(6,4,2,1,3,5,7)

链栈中为何不设置头结点？

答案是：教师释疑： 因为链栈是运算受限的单链表，其插入和删除操作仅限制在表头位置上进行，由于只能在链表头部进行操作，故链栈不需设置头结点。

要在［0..n-l］的向量空间中建立两个栈stackl和stack2，请回答： (1)应该如何设计这两个栈才能充分利用整个向量空间？ (2)若stackl的栈顶指针为topl,stack2的栈顶指针为top2，如果需要充分利用整个向量空

答案是：教师释疑： (1)采用双向栈的形式，stack1的栈底设置在从数组下标为0的元素处，stack2的栈底设置在数组下标为n-1的元素处(2)top1=-1top2=ntop1-1=top2或top1=0top2=n-1top1-1=top2

在一个长度为100的顺序表中删除第10个元素时，需要移动 个元素。

答案是：教师释疑： 90

如果需要对线性表频繁进行_____操作，则不宜采用顺序存储结构。长度为n的线性表采用单链表结构存储时，在等概率情况下查找第i个元素的时间复杂度是___。

答案是：教师释疑： 插入或删除，O(n)

将两个长度分别为m和n的递增有序单链表，归并成一个按元素递减有序的单链表，可能达到的最好的时间复杂度是 _____。在一个长度为n的单链表L中，删除链表中*p的前驱结点的时间复杂度为_________。

答案是：教师释疑： O(m+n),O(n)

在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head=___。

答案是：教师释疑： p－＞next－＞next

输入线性表的n个元素建立带头结点的单链表，其时间复杂度为___________。在双向循环链表中插入一个新的结点时，应修改_________个指针域的值。

答案是：教师释疑： O(n),4

在等概率情况下，在长度为n的顺序表中插入和删除一个结点需平均移动___________个结点和___________个结点，具体的移动次数取决于___________和___________。

答案是：教师释疑： n/2，(n-1)/2，顺序表的长度n，插入或删除的位置i。i越接近n则所需移动的结点数越少。

已知顺序表的表结构定义如下： #define MAXLEN 100 typedef int KeyType; typedef struct { KeyType key; InfoType otherinfo;

答案是：教师释疑： (1)-1,3 (2)二分查找给定的关键字，若存在则返回关键字在表中的位置(或下标)，否则返回-1。

阅读下列算法，并回答下列问题： (1)该算法采用何种策略进行排序? (2)算法中R[n+1]的作用是什么? Typedef struct { KeyType key; infoType otherinfo; } no

答案是：教师释疑： (1)插入排序(2)作为监视哨(或哨兵)