11.1 选择题
（833） 下面关于算法说法错误的是_______。
a. 算法最终必须由计算机程序实现
b. 为解决某问题的算法同为该问题编写的程序含义是相同的
c. 算法的可行性是指指令不能有二义性
d. 以上几个都是错误的
（834） 下面说法错误的是______.
a. 算法原地工作的含义是指不需要任何额外的辅助空间
b. 在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法
c. 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界
d. 同一个算法，实现语言的级别越高，执行效率就越低
（835） 在下面的程序段中，对x的赋值语句的频度为_____。
for (int i; i<n; i++)
{
for (int j=o; j<n; j++)
{
x:=x+1;
}
}
a. 0(2n) b. 0(n) c. 0(n2) d. O(log2n)
（836） 下面说法正确的是______。
a. 数据元素是数据的最小单位；
b. 数据元素是数据的最小单位；
c. 数据的物理结构是指数据在计算机内的实际存储形式
d. 数据结构的抽象操作的定义与具体实现有关
（837） 下面说法正确的是_______。
a. 在顺序存储结构中，有时也存储数据结构中元素之间的关系
b. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高
c. 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立
d. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构
（838） 下述_____是顺序存储结构的优点。
a. 存储密度大
b. 插入运算方便
c. 删除运算方便
d. 可方便地用于各种逻辑结构的存储表示
（839） 下面关于线性表的叙述中，错误的是_____。
a. 线性表采用顺序存储，必须占用一片连续的存储单元
b. 线性表采用顺序存储，便于进行插入和删除操作
c. 线性表采用链接存储，不必占用一片连续的存储单元
d. 线性表采用链接存储，便于插入和删除操作
（840） 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用_______存储方式最节省时间。
a. 顺序表 b. 双链表 c. 带头结点的双循环链表 d. 单循环链表
（841） 静态链表中指针表示的是______。
a. 内存地址 b. 数组下标 c. 下一元素地址 d. 左、右孩子地址
（842） 下面的叙述不正确的是_______。
a. 线性表在链式存储时，查找第i个元素的时间同i的值成正比
b. 线性表在链式存储时，查找第i个元素的时间同i的值无关
c. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比
d. 线性表在顺序存储时，查找第i个元素的时间同i的值无关
（843） 下面说法错误的是_____。
a. 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。
b. 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。
c. 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。
d. 静态链表就是一直不发生变化的链表。
（844） 在双向链表指针p的结点前插入一个指针q的结点操作是______。
a. p->Llink=q; q->Rlink=p; p->Llink->Rlink=q; q->Llink=q；
b. p->Llink=q; p->Llink->Rlink=q; q->Rlink=p; q->Llink=p->Llink;
c. q->Rlink=p; q->Llink=p->Llink; p->Llink->Rlink=q; p->Llink=q;
d. q->Llink=p->Llink; q->Rlink=q; p->Llink=q; p->Llink=q;
（845） 下面说法正确的是______。
a. 顺序存储结构的主要缺点是不利于插入或删除操作；
b. 线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的；
c. 顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好；
d. 顺序存储方式只能用于存储线性结构。
（846） 下面说法正确的是______。
a. 线性表只能用顺序存储结构实现。
b. 为了很方便的插入和删除数据，可以使用双向链表存放数据。
c. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
d. 链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。
（847） 下面说法正确的是_________。
a. 数据元素是数据的最小单位。
b. 队列逻辑上是一个下端口和上端能增加又能减少的线性表。
c. 任何一个递归过程都可以转换成非递归过程。
d. 只有那种使用了局部变量的递归过程在转换成非递归过程时才必须使用栈。
（848） 下面说法正确的是_________。
a. 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入、删除等操作。
b. 两分法插入排序所需比较次数与待排序记录的初始排列状态相关。
c. 当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省。
d. 在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。
（849） 下面说法正确的是______。
a. 在执行某个排序算法过程中，出现了排序码朝着最终排序序列相反方向移动，则该算法是不稳定的。
b. 堆排序是稳定的排序方法。
c. 在分配排序时，最高位优先分配法比最低位优先分配法简单。
d. 最佳两叉排序树的任何子树都是最佳的。
（850） 具有N个结点的完全二叉树的深度是：_____。
a. [log2n] b.[LOG2N]/1 c. [LOG2(N/1)] d.[LOG2N]-1
（851） 用单循环链表表示队列，正确的说法是：_____。
a. 可设一个头指针使入队、出队都方便
b. 可设一个尾指针使入队、出队都方便
c. 必须设头尾指针才能使入队、出队都方便
d. 无论如何,只可能使入队方便
（852） 一个哈希函数被认为是"好的"，如果它满足条件_____。
a. 哈希地址分布均匀
b. 保证不产生冲突
c. 所有哈希地址在表长范围内
d. 满足(2)和(3)
（853） ISAM文件和VSAM文件属于_____。
a. 索引非排序文件
b. 索引顺序文件
c. 顺序文件
d. 散列文件
（854） 在下述排序算法中_____算法是稳定的排序算法。
a. 希尔排序
b. 快速排序
c. 冒泡排序
d. 堆排序
（855） 在下述三种排序算法中，所需辅助存储量最多的是_____，所需存储量最少的是_____，平均速度最快的是_____。
a. 堆排列 b. 快速排列 c.归并排列
（856） 存贮稀疏图的数据结构常有的是____。
a. 邻接矩阵 b. 三元组 c. 邻接表 d. 十字链表
（857） 内部排序多个关键字的文件，最坏情况下最快的排列方法是_____,相应的时间复杂度为______,该算法是的稳定性_____。
a. 快速排序 b. 插入排序 c. 归并排序 d. 简单选择排序
e. O(nlog2(n)) f. O(n^2) g. O(n^2log2(n)) h. O(n) i. 稳定 j. 不稳定
（858） 倒排文件包含若干个倒排表，倒排表的内容是______。
a. 一个关键字值和关键字的记录地址；
b. 一个属性值和该属性的一个记录地址；
c. 一个属性值和该属性的全部属性地址；
d. 多个关键字值和它们对应的某个记录的地址。
（859） 在下述几种树当中,_____可以表示静态查找表.
a. 次优查找树;
b. 二叉排序树;
c. B-树
d. 平衡二叉树
（860） 选择填空：
(1). 在文件局部有序或文件长度较小的情况下,最优内部排序的方法是____.
(2). 快速排序在最坏的情况下,时间复杂度是____,____的性能差;
(3). 就平均时间而言,____最佳.
a.: (1)直接插入排序 (2)起泡排序 (3)简单选择排序;
b.: (1)O(nlog(n)) (2)O(n^2) (3)O(n^3)
c.: (1)堆排序 (2)起泡排序 (3)选择排序.
d.: (1)堆排序 (2)快速排序 (3) 归并排序.
（861） 算法的时间复杂度取决于_____。
a. 问题的规模
b. 待处理数据的初态
c. both a and b
（862） 假定有k个关键字互为同义词,若用线性探测法把这k个关键字存入散列表中,至少要进行____次探测。
a. k-1
b. k
c. k=1
d. k(k+1)/2
（863） 若需要在O(nlog2(n))的时间内完成对数组的排序,且要求排序是稳定的,则可选择的排序方法是:
a. 快速排序
b. 堆排序
c. 归并排序
d. 直接插入排序
（864） 将两个各有n个元素的有序表归并成一个有序表,其最少的比较次数是_____。
a. n
b. 2n-1
c. 2n
d. n-1
（865） 下述二叉树中,____满足性质:从任意结点出发到根的路径上所经过的结点序列按其关键字有序。
a. 二叉排序树
b. 哈夫曼树
c. AVL树
d. 堆
（866） 若在线性表中采用折半查找法查找元素，该线性表应该_____。
a. 元素按值有序
b. 采用顺序存储结构"
c. 元素按值有序，且采用顺序存储结构
d. 元素按值有序，且采用链式存储结构
（867） 若二叉树采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，利用____遍历方法最合适。
a. 前序 b.中序 c.后序 d. 按层次
（868） 对二叉排序树进行____遍历，可以得到该二叉树所有结点构成的排序序列。
a. 前序 b. 中序 c.后序 d. 按层次
（869） 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为____排序法。
a. 插入 b. 选择 c. 谢尔 d. 二路归并
（870） 排序趟数与序列的原始状态有关的排序方法是____排序法。
a. 插入 b. 选择 c. 泡 d. 快速
（871） 下面给出的四种排序法中____排序法是不稳定性排序法。
a. 插入 b. 泡 c. 二路归并 d. 堆积
（872） 下面哪一个方法可以判断出一个有向图中是否有环（回路）？
a. 深度优先遍历 b. 拓朴排序 c. 求最短路径 d. 求关键路径
（873） 下面关于程序设计风格的说法正确的是______。
a. 中序遍历一棵二叉排序树的节点就可得到排好序的节点序列。
b. 顺序存储方式只能用于存储线性结构。
c. 顺序查找法适用于存储结构为顺序或链接存储的线性表。
d. 栈和队列都是限制存取点的线性结构。
（874） 已知变量定义：
char S[3]="AB"
char *P;
在执行了语句P＝S之后，*（P＋2）的值是______。
a. 'B'
b. '\0'
c. 不确定
d. 字符'B'的地址
（875） 下面程序段的时间复杂度为______。
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
A[i][j]=i*j;
}
}
a. O(m2) b. O(n2) c. O(m*n) d. O(m+n)
（876） 下列程序为将一条数据插入栈上：
void add(int top,element item)
{
if (top>=MAX_STACK_SIZE-1)
return stack_full();
stack[ ]=item;
}
则在stack[ ]的中括号内横线上的正确内容应为：_____。
a. ++*top b. *top++ c. *top-- d. *top
（877） 有如下函数：
void fun(struct node h1,struct node h2)
{
struct node *t;
t=h1;
while (t->next != '\0')
t = t->next;
t->next = h2;
}
其中形参h1和h2分别指向2个不同链表的第一个结点，此函数的功能是：______。
a. 将链表h2接到链表h1后
b. 将链表h1接到链表h2后
c. 找到链表h1的最后一个结点由指针返回
d. 将链表h1拆分成两个链表
（878） 一个栈的入栈序列是abcde，则栈的不可能输出序列是： __。
a. edcba b. decba
c. dceab d. abcde
（879） 下面说法正确的是_____。
a. 队列逻辑上是一个表头和表尾既能插入又能删除的线性表。
b. 任何一个递归过程都可以转换成非递归过程。
c. 与n个键值的集合{k1,k2,…,kn}相对应的堆是唯一的。
d. 在索引顺序表上实现分块查找，在等概率查找情况下，其查找长度只与表中元素个数有关，而与每块中元素个数无关。
（880） 下面说法正确的是_____。
a. 在10万个随机排列的数据中，要选出5个最小的数，采用快速排序比采用Shell排序、堆排序及各种直接排序法都快。
b. 哈希表查找无需进行关键字的比较。
c. 在执行某个排序过程中，出现排序码朝着最终位置相反方向移动，则该算法是不稳定的。
d. B树查找算法的时间复杂性为O（n）。
（881） 下列有关线性表的叙述中，正确的是_____。
a. 线性表中的元素之间隔是线性关系
b. 线性表中至少有一个元素
c. 线性表中任何一个元素有且仅有一个直接前趋
d. 线性表中任何一个元素有且仅有一个直接后继
（882） 下列关于串的叙述中，正确的是_____。
a. 一个串的字符个数即该串的长度
b. 一个串的长度至少是1
c. 空串是由一个空格字符组成的串
d. 两个串S1和S2若长度相同，则这两个串相等
（883） 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
（884） 以数组Q[0..m－1]存放循环队列中的元素，变量rear和qulen分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数，队列第一个元素的实际位置是____。
a. rear－qulen
b. rear－qulen＋m
c. m－qulen
d. 1＋（rear＋m－qulen）mod m
（885） 高二叉树根结点的层次为1，所有含有15个结点的二叉树中，最小高度是_______。
a. 6 b. 5 c. 4 d. 3
（886） 下列四种排序方法中，不稳定的方法是_____。
a. 直接插入排序 b. 冒泡排序
c. 归并排序 d. 直接选择排序
（887） 设有一个长度为100的已排好序的表，用二分查找进行查找，若查找不成功，至少比较____次。
a. 9 b. 8 c. 7 d. 6
（888） 一棵二叉排序树T，用_____方法进行遍历，可以得到各结点键值的递增序列。
a. 先根遍历 b. 中根遍历
c. 层次遍历 d. 后根遍历
（889） 设结点x和结点y是二叉树T中的任意两个结点，若在先根序列中x在y之前，而在后根序列中x在y之后，则x和y的关系是_____。
a. x是y的左兄弟 b. x是y的右兄弟
c. x是y的祖先 d. x是y的后代
（890） 下面说法正确的是______。
a. 数据的机内表示称为数据的存储结构。
b. 线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。
c. 二叉树中任何一个结点的度都是2。
d. 由二叉树结点的先根序列的后根序列可以唯一地确定一棵二叉树。
（891） 下面说法正确的是______。
a. 用直接选择排序方法分别对序列S1＝（1，2，3，4，5，6，7）和序列S2＝（7，5，3，2，4，1，6）进行排序，两者的比较次数不相同。
b. 一棵哈夫曼树中不存在度为1的结点。
c. 用二分查找法对一个顺序表进行查找，这个顺序表可以是按各键值排好序的，也可以是没有按键值排好序的。
d. 顺序文件适宜顺序存取，不适宜随机存取。
（892） 下列算法中，某一轮结束后未必能选出一个元素放在其最终位置上的是______。
a. 堆排序 b. 冒泡排序 c. 直接插入排序 d. 快速排序
（893） _____是不稳定的排序方法。
a. 冒泡排序 b. 归并排序 c. 堆排序 d. 选择排序
（894） 从逻辑上，可以将数据结构分为_____两类。
a. 动态表和静态表 b. 顺序结构和链式结构
c. 线性结构和非线性结构 d. 动态结构和静态结构
11.2 填空题
（895） 下面程序段的时间复杂度为________。
sum=1；
for (i=0; sum<n; i++)
{
sum+=1;
}
（896） 下列程序的功能是创建单向链表，请补充完整。
#include <stdio.h>
#include <alloc.h>
struct link
{
char name[10];
int mark;
struct link * next;
};
void insert(char * name, int mark);
struct link * head = NULL;
main()
{
char name[10];
int mark;
struct link *t;
while (1)
{
scanf("%s %d", name, &mark);
if (strcmp(name, "#") == 0 )
{
break;
}
______(1)_______;
}
for (t=head; ______(2)_______)
{
printf("<%s>: %d\n", t->name, t->mark);
}
}
void insert(char * name, int mark)
{
struct link * p;
p = ______(3)_______ ;
strcpy(p->name, name);
p->mark = mark;
______(4)_______;
if ( head != NULL )
{
______(5)_______;
}
head = p;
}
（897） 用循环链表表示的队列长度为n， 若只设头指针,则出队和入队的时间复杂度分别是______和_____； 若只设尾指针,则出队和入队的时间复杂度分别是_____和_____。
（898） 在n个记录的有序顺序表中进行折半查找,最大的比较次数是______。
（899） 仔细阅读下列程序，在空白处填入适当的语句。
函数match(s,t)完成在字符串s中寻找与t匹配的字符，若存在一个匹配，则返回t在字符串s中的下标；否则，返回-1。其中，字符指针*b始终指向s的第一元素。
Match(s,t)
Char s,t;
｛
char *b=s;
char *p, *r;
for _________________________________
｛
for (p=s, r=t; *r!=`\0` && *p= =*r; p++, r++);
if__________________________________
return(s-b);
｝
return(-1);
｝
（900） 补充下列程序：设一棵二叉序列树b，下列算法函数是实现在b中插入一个结点s。
函数：
void insert（btree *b，btree *s）
{
if（b == NULL） b = s；
else
if（s->data == b->data） return();
else
if(s->data < b->data)
；
else
；
}
（901） 一个n×n的下三角矩阵A中的元素aij（i≥j，1≤i，j≤n）按行存于一个一维数组B[1..n（n＋1）/2]中，对其中的任一元素aij，若在B中的位置为k，则k＝__________。
（902） 含有100个结点的树有__________条边。
（903） 设一个闭散列表的容量为m，用线性控测法解决冲突，要插入一个键值，若插入成功，至多要进行__________次比较。
（904） 设二维数组M：array[-1..4，0..3]of integer，每个元素（整数）占２个存储单元，元素按行的顺序存储，数组的起始地址为200，元素M[2，1]的地址是__________。
（905） 线性表L＝（a1，a2，...，an）采用顺序存储，假定在不同的n＋1个位置上插入的概率相同，则插入一个新元素平均需要移动的元素个数是__________。
（906） 设栈S和队列Q的初始状态皆为空，元素a1，a2，a3，a4，a5和a6依次通过一个栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3，a5，a4，a6，a2，a1则栈S至少应该容纳__________个元素。
（907） 两个序列如下：
L1 ＝ {25，57，48，37，92，86，12，33}
L2 ＝ {25，37，33，12，48，57，86，92}
用冒泡排序方法分别对序列L1和L2进行排序，交换次序较少的是序列________。
（908） 将一棵有50个结点的完全二叉树从根结点开始，由根向下，每一层从左至右，顺序地存储在一个一维数组bt[1..50]中，这棵二叉树最下面一层上最左边一个结点存储在数组元素__________中。
（909） 一个索引文件由__________两部分组成。
11.3 问答与设计
（910） 说明线性插入排序的算法及时间、空间复杂度
（911） 说明折半插入排序的算法及时间、空间复杂度
（912） 说明堆排序的算法及时间、空间复杂度
（913） 说明希尔排序的算法及时间、空间复杂度
（914） 说明快速排序的算法及时间、空间复杂度
（915） 说明基数排序的算法及时间、空间复杂度
（916） 说明交换排序的算法及时间、空间复杂度
（917） 说明选择排序的算法及时间、空间复杂度
（918） 说明归并排序的算法及时间、空间复杂度
（919） 说明分布排序的算法及时间、空间复杂度
（920） 说明顺序查找的算法及时间、空间复杂度
（921） 说明折半查找的算法及时间、空间复杂度
（922） 说明分块查找的算法及时间、空间复杂度
（923） 说明比较查找的算法及时间、空间复杂度
（924） 说明基数查找的算法及时间、空间复杂度
（925） 说明哈希查找的算法及时间、空间复杂度
（926） 怎样查找链表中的数据?
（927） 在一个包含 n 个元素的数组 M 中查找一个元素 x。 算法假设 M 已经按升序排列了，请写出二分搜索算法的步骤。
（928） 已知链表节点的类型定义如下，需要按照成员value从小到大进行排序，请写出算法：
#include<stdio.h>
#include<stdlib.h>
typedef struct STRUCT
{
int value;
struct STRUCT *next;
}TS;
（929） 什么是算法？算法的主要特点是什么？
（930） 如何评价一个算法？
（931） 什么是顺序存储结构？什么是链式存储结构？
（932） 线性表的顺序存储结构和链式存储结构各有什么特点？
（933） 若顺序表A中的数据元素按升序排列，要求将x插入到顺序表中的合适位置，以保证表的有序性，试给出其算法。
（934） 试将一个无序的线性表A=(11,16,8,5,14,10,38,23)转换成一个按升序排列的有序线性表（用链表实现）。
（935） 简述栈和线性表的区别和联系。
（936） 何为栈和队列？简述两者的区别和联系。
（937） 若依次读入数据元素序列{a,b,c,d}进栈，进栈过程中允许出栈,试写出各种可能的出栈元素序列。
（938） 将下列各算术运算式表示成波兰式和逆波兰式：
(A*(B+C)+D)*E-F*G
A*(B-D)+H/(D+E)-S/N*T
(A-C)*(B+D)+(E-F)/(G+H)
（939） 写出算术运算式3+4/25*8-6的操作数栈和运算符栈的变化情况。
（940） 若堆栈采用链式存储结构，初始时为空，试画出a,b,c,d四个元素依次进栈后栈的状态，然后再画出此时的栈顶元素出栈后的状态。
（941） 简述设计一个结点值为整数的循环队列的构思，并给出在队列中插入或删除一个结点的算法。
（942） 有一个循环队列q(n)，进队和退队指针分别为r和f；有一个有序线性表A[M]，请编一个把循环队列中的数据逐个出队并同时插入到线性表中的算法。若线性表满则停止退队并保证线性表的有序性。
（943） 设有栈stack，栈指针top=n-1，n>0；有一个队列Q(m)，其中进队指针r，试编写一个从栈stack中逐个出栈并同时将出栈的元素进队的算法。
（944） 两个字符串相等的充要条件是什么？
（945） 串有哪几种存储结构？
（946） 设字符串采用块链存储结构，块链中每个结点存放m（m=4）个字符，试写出实现字符串删除的算法。
（947） 设s1和s2是用结点大小为1的单链表表示的串，试写出找出s2中第一个不在s1中出现的字符的算法。
（948） 按行优先存储方式，写出三维数组A[3][2][4]在内存中的排列顺序及地址计算公式（假设每个数组元素占用L个字节的内存单元，a[0][0][0]的内存地址为Loc(a[0][0][0])）。
（949） 按列优先存储方式，写出三维数组A[3][2][4]在内存中的排列顺序及地址计算公式（假设每个数组元素占用L个字节的内存单元，a[0][0][0]的内存地址为Loc(a[0][0][0])）。.
（950） 设有上三角矩阵An′n，它的下三角部分全为0，将其上三角元素按行优先存储方式存入数组B[m]中(m足够大)，使得B[k]=a[i][j]，且有k=f1(i)+f2(j)+c。试推出函数f1、f2及常数c（要求f1和f2中不含常数项）。
（951） 若矩阵Am′n中的某个元素A[i][j]是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该矩阵中的一个马鞍点。假设以二维数组存储矩阵Am′n，试编写求出矩阵中所有马鞍点的算法，并分析你的算法在最坏情况下的时间复杂度。
（952） 试写一个算法，查找十字链表中某一非零元素x。
（953） 广义表是线性结构还是非线性结构?为什么?
（954） 画出下列广义表的图形表示
(1) A(b,(A,a,C(A)),C(A))
(2) D(A( ),B(e),C(a,L(b,c,d)))
（955） 若逻辑结构相同但存储结构不同，则为不同的数据结构。这样的说法对吗？举例说明之。
（956） 在给定的逻辑结构及其存储表示上可以定义不同的运算集合，从而得到不同的数据结构。这样说法对吗？举例说明之。
（957） 评价各种不同数据结构的标准是什么？
（958） 评价一个好的算法，需要从哪几方面来考虑的？
（959） 什么是算法的时间复杂性？
（960） 什么是抽象数据类型？
（961） 数据结构与数据类型有什么区别？
（962） 数据的存储结构由哪四种基本的存储方法实现？
（963） 运算是数据结构的一个重要方面。试举一例，说明两个数据结构的逻辑结构和存储方式完全相同，只是对于运算的定义不同。因而两个结构具有显著不同的特性，是两个不同的结构。
（964） 在编制管理通讯录的程序时, 什么样的数据结构合适? 为什么?
（965） 试举一例，说明对相同的逻辑结构,同一种运算在不同的存储方式下实现，其运算效率不同。
（966） 有实现同一功能的两个算法A1和A2，其中A1的时间复杂度为Tl=O(2n)，A2的时间复杂度为T2=O(n2)，仅就时间复杂度而言，请具体分析这两个算法哪一个好。
（967） 分析下面程序段中循环语句的执行次数。
Int i= 0, s = 0, n = 100;
Do
{
i:=i+1;
s:=s+10*i;
}while ((I<n) && (s<n))
（968） 根据下面程序，回答下面问题：
(1) 试指出f(n)值的大小，并写出f(n) 值的推导过程;
(2) 假定n= 5，试指出f(5)值的大小和执行f(5)时的输出结果。
int f(int n)
{
int i, j, k, sum= 0;
for(i=l; i<n+1; i++)
{
for(j=n; j>i-1; j--)
{
for(k=1; k<j+1; k++ )
{
sum++;
printf("sum=%d\n", sum)；
}
}
}
return (sum);
}
（969） 设n是偶数，试计算运行下列程序段后m的值并给出该程序段的时间复杂度。
int m = 0;
For (int i = 0; i < n; i++)
{
for (int j = 2*i, j < n; j++)
{
m = m + 1;
}
}
（970） 试给出下面两个算法的运算时间。
a. for (int I = 0; I < n; I++)
{
x++;
}
b. for (int I = 1; I < n; I++)
{
for (int j = 1; j < n; j++)
{
x++;
}
}
（971） 快速排序的最大递归深度是多少？最小递归深度是多少？
（972） 对链表设置表头节点的作用是什么？
（973） 有五个数依次进栈：1,2,3,4,5.在各种出栈的序列中，以3,4先出的序列有哪几个。（３在４之前出栈）
（974） 试写出进栈操作，出栈操作算法的时间复杂性。
（975） 已知ＫＭＰ串匹配算法的模式串是AABBAAB,试写出改进后的NEXT信息帧。
（976） 某整型数组Ａ的１０个元素值依次为6,2,9,7,3,8,4,5,0,1,用下列各排序方法，将Ａ中元素由小到大排序。
(1) 取第一个元素值６作为分割数，(2) 试写出快速排序第一次分隔后Ａ中的结果。
(3) 用堆排序，(4) 试写出将第一个选出的数据放在Ａ的最后位置上，(5) 将Ａ调整成堆后的Ａ中结果。
(6) 用基数为３的基数排序法，(7) 试写出第一次分配和收集后Ａ中的结果。
（977） 已知某排序平衡二叉树Ｔ具有下列特点：
(1) 结点的关键字均在1到9范围内；
(2) 在Ｔ中存在一个关键字为n1的叶结点，若删去该结点，立即插入一个关键字为n1的结点，得到的平衡树与原Ｔ不相同；
(３) 在Ｔ中存在另一个关键字为n2的非叶结点，删去它，并立即插入n2结点，得到与原Ｔ相同的平衡树；
(４) 在Ｔ中插入某n3结点后立即删除它，得到的平衡树与原Ｔ不相同。
试画出具有上述特点的最简单（结点个数最少）的平衡树Ｔ，并写明n1,n2,n3分别等于几？
（978） 设一单向链表的头指针为head，链表的记录中包含着整数类型的key域,试设计算法，将此链表的记录按照key递增的次序进行就地排序。
（979） 在排序连续顺序文件中采用折半查找方法查找记录存在与否的过程可以借助于一棵平衡二叉树(也称判定树)来模拟，树中结点的值为记录在文件中的位置序号。
(1) 若文件中有l 9个记录，请画出这棵判定树；
(2) 当文件中有n个记录时，求出该判定树的深度。
（980） 试举例说明用程序设计语言描述堆栈结构时，要涉及那些问题？
（981） 在程序设计语言中实现递归的条件是什么？编写递归子程序，应注意什么？
（982） 动态查找树，有哪几项基本操作？
（983） 举例说明有向图的最短路径算法常用于哪几种情形？
(1) 中断和死锁
(2) 变量与表达式
(3) 对象与属性
(4) 虚拟地址与实地址
(5) 数据的物理结构和逻辑结构
（984） 内存中一片连续空间（不妨假设地址从1到m），提供给两个栈S1和S2使用，怎样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。
（985） 一棵共有n个结点的树，其中所有分枝结点的度均为k，求该树中叶子结点的子数。
（986） 设有一个由正整数组成的无序（向后）单链表，编写完成下列功能的算法：
(1) 找出最小值结点，且打印该数值；
(2) 若该数值是奇数，则将其与直接后继结点的数值交换；
(3) 若该数值是偶数，则将其直接后继结点删除；
（987） 给出下算法的时间复杂度：
main( )
{
int x , n , y ;
scanf("%d", &n);
x=n;
y=0;
while (x >= (y+1)(y+1))
{
y++;
}
}
（988） 试举例说明对相同的逻辑结构，同一种运算在不同的存储方式下实现，其运算效率不同。
（989） 对链表设置表头结点的作用是什么？（至少说出2条好处）
（990） 快速排序在什么情况下排序算法产生恶化，原因是什么？
（991） 设在一个有关串的程序编码当中，有如下定义与赋值：
const char A[] = {'a','b','c','\0'};
char B[] = {'a','b','c','d','\0'};
… …
for (i=0; i<4; i++)
{
A[i] = 'a';
B[i] = 'b';
}
… ...
在该程序编码中是否有错？为什么？
（992） 若A为一下三角矩阵数组，则采用以行为主和以列为主的数据存放方式哪一种更合适？为什么？
（993） 线性表A和B均是按元素值递增有序排列，均以单链表作存储结构。请编写一算法将表A和表B归并成一个按元素值递减有序排列的线性表C（允许表中含有值相同的元素），并要求利用原表空间。
（994） 编写一个算法，对于输入的十进制非负整数，将它的八进制表示打印出来。
（995） 编写函数strcmp(char * s1, char * s2)。若s1和s2均是数字串（包括+/-号），则按照十进制整数大小进行比较；否则按照Ascii序进行比较。s1大于/等于/小于s2时，分别输出1/0/-1。可以直接调用atoi函数。
（996） 请回答下列关于堆（Heap）的一些问题：
(1) 堆的存储表示是顺序的，还是链接的？
(2) 设有一个最小堆，即堆中任意节点的关键码均大于它的左子女和右子女的关键码。其具有最大值的元素可能在什么地方？
(3) 对n个元素进行初始建堆的过程中，最多做多少次数据比较（不用大O表示法）？
（997） 快速排序的时间复杂度是多少？试推导之。
（998） 从键盘上输入一串正整数，以-1为输入结束的标志，试设计一个算法，生成一棵二叉排序树（即依次把该序列中的结点插入二叉排序树）。
（999） 试设计一个算法，在中序线索二叉树中求指定结点P在后序遍历序列中的前驱结点。要求算法为非递归的，空间复杂度为O（1）。
（1000） 修改冒泡排序法以实现双向冒泡排序。即第一次把最大记录放到表尾，第二次将最小记录放到表头，如此反复进行，直至排序结束。试编写此算法。
（1001） 针对以下情况确定非递归的归并排序的运行时间(数据比较次数与移动次数):
(1) 输入的n个数据全部有序;
(2) 输入的n个数据全部逆向有序;
(3) 随机地输入n个数据.
（1002） 说明下列算法的功能：
void a1(stack &s)
{
int i, n, a[255];
n = 0;
while (!stackempty(s))
{
n++;
pos(s, a[n];
}
for (i = 1; i <= n; i++)
{
push(s, a[i]);
}
}
（1003） 说明下列算法的功能：
void a2(stak &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);
}
}
（1004） 说明下列算法的功能：
void change(linklist &head)
{
linklist q, p;
if (head && head->next)
{
q = head;
head = head->next;
p = head;
while (p->next) p = p->next;
p->next = q;
q->next = NULL;
}
}
（833） 下面关于算法说法错误的是_______。
a. 算法最终必须由计算机程序实现
b. 为解决某问题的算法同为该问题编写的程序含义是相同的
c. 算法的可行性是指指令不能有二义性
d. 以上几个都是错误的
（834） 下面说法错误的是______.
a. 算法原地工作的含义是指不需要任何额外的辅助空间
b. 在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法
c. 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界
d. 同一个算法，实现语言的级别越高，执行效率就越低
（835） 在下面的程序段中，对x的赋值语句的频度为_____。
for (int i; i<n; i++)
{
for (int j=o; j<n; j++)
{
x:=x+1;
}
}
a. 0(2n) b. 0(n) c. 0(n2) d. O(log2n)
（836） 下面说法正确的是______。
a. 数据元素是数据的最小单位；
b. 数据元素是数据的最小单位；
c. 数据的物理结构是指数据在计算机内的实际存储形式
d. 数据结构的抽象操作的定义与具体实现有关
（837） 下面说法正确的是_______。
a. 在顺序存储结构中，有时也存储数据结构中元素之间的关系
b. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高
c. 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立
d. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构
（838） 下述_____是顺序存储结构的优点。
a. 存储密度大
b. 插入运算方便
c. 删除运算方便
d. 可方便地用于各种逻辑结构的存储表示
（839） 下面关于线性表的叙述中，错误的是_____。
a. 线性表采用顺序存储，必须占用一片连续的存储单元
b. 线性表采用顺序存储，便于进行插入和删除操作
c. 线性表采用链接存储，不必占用一片连续的存储单元
d. 线性表采用链接存储，便于插入和删除操作
（840） 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用_______存储方式最节省时间。
a. 顺序表 b. 双链表 c. 带头结点的双循环链表 d. 单循环链表
（841） 静态链表中指针表示的是______。
a. 内存地址 b. 数组下标 c. 下一元素地址 d. 左、右孩子地址
（842） 下面的叙述不正确的是_______。
a. 线性表在链式存储时，查找第i个元素的时间同i的值成正比
b. 线性表在链式存储时，查找第i个元素的时间同i的值无关
c. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比
d. 线性表在顺序存储时，查找第i个元素的时间同i的值无关
（843） 下面说法错误的是_____。
a. 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。
b. 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。
c. 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。
d. 静态链表就是一直不发生变化的链表。
（844） 在双向链表指针p的结点前插入一个指针q的结点操作是______。
a. p->Llink=q; q->Rlink=p; p->Llink->Rlink=q; q->Llink=q；
b. p->Llink=q; p->Llink->Rlink=q; q->Rlink=p; q->Llink=p->Llink;
c. q->Rlink=p; q->Llink=p->Llink; p->Llink->Rlink=q; p->Llink=q;
d. q->Llink=p->Llink; q->Rlink=q; p->Llink=q; p->Llink=q;
（845） 下面说法正确的是______。
a. 顺序存储结构的主要缺点是不利于插入或删除操作；
b. 线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的；
c. 顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好；
d. 顺序存储方式只能用于存储线性结构。
（846） 下面说法正确的是______。
a. 线性表只能用顺序存储结构实现。
b. 为了很方便的插入和删除数据，可以使用双向链表存放数据。
c. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
d. 链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。
（847） 下面说法正确的是_________。
a. 数据元素是数据的最小单位。
b. 队列逻辑上是一个下端口和上端能增加又能减少的线性表。
c. 任何一个递归过程都可以转换成非递归过程。
d. 只有那种使用了局部变量的递归过程在转换成非递归过程时才必须使用栈。
（848） 下面说法正确的是_________。
a. 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入、删除等操作。
b. 两分法插入排序所需比较次数与待排序记录的初始排列状态相关。
c. 当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省。
d. 在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。
（849） 下面说法正确的是______。
a. 在执行某个排序算法过程中，出现了排序码朝着最终排序序列相反方向移动，则该算法是不稳定的。
b. 堆排序是稳定的排序方法。
c. 在分配排序时，最高位优先分配法比最低位优先分配法简单。
d. 最佳两叉排序树的任何子树都是最佳的。
（850） 具有N个结点的完全二叉树的深度是：_____。
a. [log2n] b.[LOG2N]/1 c. [LOG2(N/1)] d.[LOG2N]-1
（851） 用单循环链表表示队列，正确的说法是：_____。
a. 可设一个头指针使入队、出队都方便
b. 可设一个尾指针使入队、出队都方便
c. 必须设头尾指针才能使入队、出队都方便
d. 无论如何,只可能使入队方便
（852） 一个哈希函数被认为是"好的"，如果它满足条件_____。
a. 哈希地址分布均匀
b. 保证不产生冲突
c. 所有哈希地址在表长范围内
d. 满足(2)和(3)
（853） ISAM文件和VSAM文件属于_____。
a. 索引非排序文件
b. 索引顺序文件
c. 顺序文件
d. 散列文件
（854） 在下述排序算法中_____算法是稳定的排序算法。
a. 希尔排序
b. 快速排序
c. 冒泡排序
d. 堆排序
（855） 在下述三种排序算法中，所需辅助存储量最多的是_____，所需存储量最少的是_____，平均速度最快的是_____。
a. 堆排列 b. 快速排列 c.归并排列
（856） 存贮稀疏图的数据结构常有的是____。
a. 邻接矩阵 b. 三元组 c. 邻接表 d. 十字链表
（857） 内部排序多个关键字的文件，最坏情况下最快的排列方法是_____,相应的时间复杂度为______,该算法是的稳定性_____。
a. 快速排序 b. 插入排序 c. 归并排序 d. 简单选择排序
e. O(nlog2(n)) f. O(n^2) g. O(n^2log2(n)) h. O(n) i. 稳定 j. 不稳定
（858） 倒排文件包含若干个倒排表，倒排表的内容是______。
a. 一个关键字值和关键字的记录地址；
b. 一个属性值和该属性的一个记录地址；
c. 一个属性值和该属性的全部属性地址；
d. 多个关键字值和它们对应的某个记录的地址。
（859） 在下述几种树当中,_____可以表示静态查找表.
a. 次优查找树;
b. 二叉排序树;
c. B-树
d. 平衡二叉树
（860） 选择填空：
(1). 在文件局部有序或文件长度较小的情况下,最优内部排序的方法是____.
(2). 快速排序在最坏的情况下,时间复杂度是____,____的性能差;
(3). 就平均时间而言,____最佳.
a.: (1)直接插入排序 (2)起泡排序 (3)简单选择排序;
b.: (1)O(nlog(n)) (2)O(n^2) (3)O(n^3)
c.: (1)堆排序 (2)起泡排序 (3)选择排序.
d.: (1)堆排序 (2)快速排序 (3) 归并排序.
（861） 算法的时间复杂度取决于_____。
a. 问题的规模
b. 待处理数据的初态
c. both a and b
（862） 假定有k个关键字互为同义词,若用线性探测法把这k个关键字存入散列表中,至少要进行____次探测。
a. k-1
b. k
c. k=1
d. k(k+1)/2
（863） 若需要在O(nlog2(n))的时间内完成对数组的排序,且要求排序是稳定的,则可选择的排序方法是:
a. 快速排序
b. 堆排序
c. 归并排序
d. 直接插入排序
（864） 将两个各有n个元素的有序表归并成一个有序表,其最少的比较次数是_____。
a. n
b. 2n-1
c. 2n
d. n-1
（865） 下述二叉树中,____满足性质:从任意结点出发到根的路径上所经过的结点序列按其关键字有序。
a. 二叉排序树
b. 哈夫曼树
c. AVL树
d. 堆
（866） 若在线性表中采用折半查找法查找元素，该线性表应该_____。
a. 元素按值有序
b. 采用顺序存储结构"
c. 元素按值有序，且采用顺序存储结构
d. 元素按值有序，且采用链式存储结构
（867） 若二叉树采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，利用____遍历方法最合适。
a. 前序 b.中序 c.后序 d. 按层次
（868） 对二叉排序树进行____遍历，可以得到该二叉树所有结点构成的排序序列。
a. 前序 b. 中序 c.后序 d. 按层次
（869） 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为____排序法。
a. 插入 b. 选择 c. 谢尔 d. 二路归并
（870） 排序趟数与序列的原始状态有关的排序方法是____排序法。
a. 插入 b. 选择 c. 泡 d. 快速
（871） 下面给出的四种排序法中____排序法是不稳定性排序法。
a. 插入 b. 泡 c. 二路归并 d. 堆积
（872） 下面哪一个方法可以判断出一个有向图中是否有环（回路）？
a. 深度优先遍历 b. 拓朴排序 c. 求最短路径 d. 求关键路径
（873） 下面关于程序设计风格的说法正确的是______。
a. 中序遍历一棵二叉排序树的节点就可得到排好序的节点序列。
b. 顺序存储方式只能用于存储线性结构。
c. 顺序查找法适用于存储结构为顺序或链接存储的线性表。
d. 栈和队列都是限制存取点的线性结构。
（874） 已知变量定义：
char S[3]="AB"
char *P;
在执行了语句P＝S之后，*（P＋2）的值是______。
a. 'B'
b. '\0'
c. 不确定
d. 字符'B'的地址
（875） 下面程序段的时间复杂度为______。
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
A[i][j]=i*j;
}
}
a. O(m2) b. O(n2) c. O(m*n) d. O(m+n)
（876） 下列程序为将一条数据插入栈上：
void add(int top,element item)
{
if (top>=MAX_STACK_SIZE-1)
return stack_full();
stack[ ]=item;
}
则在stack[ ]的中括号内横线上的正确内容应为：_____。
a. ++*top b. *top++ c. *top-- d. *top
（877） 有如下函数：
void fun(struct node h1,struct node h2)
{
struct node *t;
t=h1;
while (t->next != '\0')
t = t->next;
t->next = h2;
}
其中形参h1和h2分别指向2个不同链表的第一个结点，此函数的功能是：______。
a. 将链表h2接到链表h1后
b. 将链表h1接到链表h2后
c. 找到链表h1的最后一个结点由指针返回
d. 将链表h1拆分成两个链表
（878） 一个栈的入栈序列是abcde，则栈的不可能输出序列是： __。
a. edcba b. decba
c. dceab d. abcde
（879） 下面说法正确的是_____。
a. 队列逻辑上是一个表头和表尾既能插入又能删除的线性表。
b. 任何一个递归过程都可以转换成非递归过程。
c. 与n个键值的集合{k1,k2,…,kn}相对应的堆是唯一的。
d. 在索引顺序表上实现分块查找，在等概率查找情况下，其查找长度只与表中元素个数有关，而与每块中元素个数无关。
（880） 下面说法正确的是_____。
a. 在10万个随机排列的数据中，要选出5个最小的数，采用快速排序比采用Shell排序、堆排序及各种直接排序法都快。
b. 哈希表查找无需进行关键字的比较。
c. 在执行某个排序过程中，出现排序码朝着最终位置相反方向移动，则该算法是不稳定的。
d. B树查找算法的时间复杂性为O（n）。
（881） 下列有关线性表的叙述中，正确的是_____。
a. 线性表中的元素之间隔是线性关系
b. 线性表中至少有一个元素
c. 线性表中任何一个元素有且仅有一个直接前趋
d. 线性表中任何一个元素有且仅有一个直接后继
（882） 下列关于串的叙述中，正确的是_____。
a. 一个串的字符个数即该串的长度
b. 一个串的长度至少是1
c. 空串是由一个空格字符组成的串
d. 两个串S1和S2若长度相同，则这两个串相等
（883） 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
（884） 以数组Q[0..m－1]存放循环队列中的元素，变量rear和qulen分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数，队列第一个元素的实际位置是____。
a. rear－qulen
b. rear－qulen＋m
c. m－qulen
d. 1＋（rear＋m－qulen）mod m
（885） 高二叉树根结点的层次为1，所有含有15个结点的二叉树中，最小高度是_______。
a. 6 b. 5 c. 4 d. 3
（886） 下列四种排序方法中，不稳定的方法是_____。
a. 直接插入排序 b. 冒泡排序
c. 归并排序 d. 直接选择排序
（887） 设有一个长度为100的已排好序的表，用二分查找进行查找，若查找不成功，至少比较____次。
a. 9 b. 8 c. 7 d. 6
（888） 一棵二叉排序树T，用_____方法进行遍历，可以得到各结点键值的递增序列。
a. 先根遍历 b. 中根遍历
c. 层次遍历 d. 后根遍历
（889） 设结点x和结点y是二叉树T中的任意两个结点，若在先根序列中x在y之前，而在后根序列中x在y之后，则x和y的关系是_____。
a. x是y的左兄弟 b. x是y的右兄弟
c. x是y的祖先 d. x是y的后代
（890） 下面说法正确的是______。
a. 数据的机内表示称为数据的存储结构。
b. 线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。
c. 二叉树中任何一个结点的度都是2。
d. 由二叉树结点的先根序列的后根序列可以唯一地确定一棵二叉树。
（891） 下面说法正确的是______。
a. 用直接选择排序方法分别对序列S1＝（1，2，3，4，5，6，7）和序列S2＝（7，5，3，2，4，1，6）进行排序，两者的比较次数不相同。
b. 一棵哈夫曼树中不存在度为1的结点。
c. 用二分查找法对一个顺序表进行查找，这个顺序表可以是按各键值排好序的，也可以是没有按键值排好序的。
d. 顺序文件适宜顺序存取，不适宜随机存取。
（892） 下列算法中，某一轮结束后未必能选出一个元素放在其最终位置上的是______。
a. 堆排序 b. 冒泡排序 c. 直接插入排序 d. 快速排序
（893） _____是不稳定的排序方法。
a. 冒泡排序 b. 归并排序 c. 堆排序 d. 选择排序
（894） 从逻辑上，可以将数据结构分为_____两类。
a. 动态表和静态表 b. 顺序结构和链式结构
c. 线性结构和非线性结构 d. 动态结构和静态结构
11.2 填空题
（895） 下面程序段的时间复杂度为________。
sum=1；
for (i=0; sum<n; i++)
{
sum+=1;
}
（896） 下列程序的功能是创建单向链表，请补充完整。
#include <stdio.h>
#include <alloc.h>
struct link
{
char name[10];
int mark;
struct link * next;
};
void insert(char * name, int mark);
struct link * head = NULL;
main()
{
char name[10];
int mark;
struct link *t;
while (1)
{
scanf("%s %d", name, &mark);
if (strcmp(name, "#") == 0 )
{
break;
}
______(1)_______;
}
for (t=head; ______(2)_______)
{
printf("<%s>: %d\n", t->name, t->mark);
}
}
void insert(char * name, int mark)
{
struct link * p;
p = ______(3)_______ ;
strcpy(p->name, name);
p->mark = mark;
______(4)_______;
if ( head != NULL )
{
______(5)_______;
}
head = p;
}
（897） 用循环链表表示的队列长度为n， 若只设头指针,则出队和入队的时间复杂度分别是______和_____； 若只设尾指针,则出队和入队的时间复杂度分别是_____和_____。
（898） 在n个记录的有序顺序表中进行折半查找,最大的比较次数是______。
（899） 仔细阅读下列程序，在空白处填入适当的语句。
函数match(s,t)完成在字符串s中寻找与t匹配的字符，若存在一个匹配，则返回t在字符串s中的下标；否则，返回-1。其中，字符指针*b始终指向s的第一元素。
Match(s,t)
Char s,t;
｛
char *b=s;
char *p, *r;
for _________________________________
｛
for (p=s, r=t; *r!=`\0` && *p= =*r; p++, r++);
if__________________________________
return(s-b);
｝
return(-1);
｝
（900） 补充下列程序：设一棵二叉序列树b，下列算法函数是实现在b中插入一个结点s。
函数：
void insert（btree *b，btree *s）
{
if（b == NULL） b = s；
else
if（s->data == b->data） return();
else
if(s->data < b->data)
；
else
；
}
（901） 一个n×n的下三角矩阵A中的元素aij（i≥j，1≤i，j≤n）按行存于一个一维数组B[1..n（n＋1）/2]中，对其中的任一元素aij，若在B中的位置为k，则k＝__________。
（902） 含有100个结点的树有__________条边。
（903） 设一个闭散列表的容量为m，用线性控测法解决冲突，要插入一个键值，若插入成功，至多要进行__________次比较。
（904） 设二维数组M：array[-1..4，0..3]of integer，每个元素（整数）占２个存储单元，元素按行的顺序存储，数组的起始地址为200，元素M[2，1]的地址是__________。
（905） 线性表L＝（a1，a2，...，an）采用顺序存储，假定在不同的n＋1个位置上插入的概率相同，则插入一个新元素平均需要移动的元素个数是__________。
（906） 设栈S和队列Q的初始状态皆为空，元素a1，a2，a3，a4，a5和a6依次通过一个栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3，a5，a4，a6，a2，a1则栈S至少应该容纳__________个元素。
（907） 两个序列如下：
L1 ＝ {25，57，48，37，92，86，12，33}
L2 ＝ {25，37，33，12，48，57，86，92}
用冒泡排序方法分别对序列L1和L2进行排序，交换次序较少的是序列________。
（908） 将一棵有50个结点的完全二叉树从根结点开始，由根向下，每一层从左至右，顺序地存储在一个一维数组bt[1..50]中，这棵二叉树最下面一层上最左边一个结点存储在数组元素__________中。
（909） 一个索引文件由__________两部分组成。
11.3 问答与设计
（910） 说明线性插入排序的算法及时间、空间复杂度
（911） 说明折半插入排序的算法及时间、空间复杂度
（912） 说明堆排序的算法及时间、空间复杂度
（913） 说明希尔排序的算法及时间、空间复杂度
（914） 说明快速排序的算法及时间、空间复杂度
（915） 说明基数排序的算法及时间、空间复杂度
（916） 说明交换排序的算法及时间、空间复杂度
（917） 说明选择排序的算法及时间、空间复杂度
（918） 说明归并排序的算法及时间、空间复杂度
（919） 说明分布排序的算法及时间、空间复杂度
（920） 说明顺序查找的算法及时间、空间复杂度
（921） 说明折半查找的算法及时间、空间复杂度
（922） 说明分块查找的算法及时间、空间复杂度
（923） 说明比较查找的算法及时间、空间复杂度
（924） 说明基数查找的算法及时间、空间复杂度
（925） 说明哈希查找的算法及时间、空间复杂度
（926） 怎样查找链表中的数据?
（927） 在一个包含 n 个元素的数组 M 中查找一个元素 x。 算法假设 M 已经按升序排列了，请写出二分搜索算法的步骤。
（928） 已知链表节点的类型定义如下，需要按照成员value从小到大进行排序，请写出算法：
#include<stdio.h>
#include<stdlib.h>
typedef struct STRUCT
{
int value;
struct STRUCT *next;
}TS;
（929） 什么是算法？算法的主要特点是什么？
（930） 如何评价一个算法？
（931） 什么是顺序存储结构？什么是链式存储结构？
（932） 线性表的顺序存储结构和链式存储结构各有什么特点？
（933） 若顺序表A中的数据元素按升序排列，要求将x插入到顺序表中的合适位置，以保证表的有序性，试给出其算法。
（934） 试将一个无序的线性表A=(11,16,8,5,14,10,38,23)转换成一个按升序排列的有序线性表（用链表实现）。
（935） 简述栈和线性表的区别和联系。
（936） 何为栈和队列？简述两者的区别和联系。
（937） 若依次读入数据元素序列{a,b,c,d}进栈，进栈过程中允许出栈,试写出各种可能的出栈元素序列。
（938） 将下列各算术运算式表示成波兰式和逆波兰式：
(A*(B+C)+D)*E-F*G
A*(B-D)+H/(D+E)-S/N*T
(A-C)*(B+D)+(E-F)/(G+H)
（939） 写出算术运算式3+4/25*8-6的操作数栈和运算符栈的变化情况。
（940） 若堆栈采用链式存储结构，初始时为空，试画出a,b,c,d四个元素依次进栈后栈的状态，然后再画出此时的栈顶元素出栈后的状态。
（941） 简述设计一个结点值为整数的循环队列的构思，并给出在队列中插入或删除一个结点的算法。
（942） 有一个循环队列q(n)，进队和退队指针分别为r和f；有一个有序线性表A[M]，请编一个把循环队列中的数据逐个出队并同时插入到线性表中的算法。若线性表满则停止退队并保证线性表的有序性。
（943） 设有栈stack，栈指针top=n-1，n>0；有一个队列Q(m)，其中进队指针r，试编写一个从栈stack中逐个出栈并同时将出栈的元素进队的算法。
（944） 两个字符串相等的充要条件是什么？
（945） 串有哪几种存储结构？
（946） 设字符串采用块链存储结构，块链中每个结点存放m（m=4）个字符，试写出实现字符串删除的算法。
（947） 设s1和s2是用结点大小为1的单链表表示的串，试写出找出s2中第一个不在s1中出现的字符的算法。
（948） 按行优先存储方式，写出三维数组A[3][2][4]在内存中的排列顺序及地址计算公式（假设每个数组元素占用L个字节的内存单元，a[0][0][0]的内存地址为Loc(a[0][0][0])）。
（949） 按列优先存储方式，写出三维数组A[3][2][4]在内存中的排列顺序及地址计算公式（假设每个数组元素占用L个字节的内存单元，a[0][0][0]的内存地址为Loc(a[0][0][0])）。.
（950） 设有上三角矩阵An′n，它的下三角部分全为0，将其上三角元素按行优先存储方式存入数组B[m]中(m足够大)，使得B[k]=a[i][j]，且有k=f1(i)+f2(j)+c。试推出函数f1、f2及常数c（要求f1和f2中不含常数项）。
（951） 若矩阵Am′n中的某个元素A[i][j]是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该矩阵中的一个马鞍点。假设以二维数组存储矩阵Am′n，试编写求出矩阵中所有马鞍点的算法，并分析你的算法在最坏情况下的时间复杂度。
（952） 试写一个算法，查找十字链表中某一非零元素x。
（953） 广义表是线性结构还是非线性结构?为什么?
（954） 画出下列广义表的图形表示
(1) A(b,(A,a,C(A)),C(A))
(2) D(A( ),B(e),C(a,L(b,c,d)))
（955） 若逻辑结构相同但存储结构不同，则为不同的数据结构。这样的说法对吗？举例说明之。
（956） 在给定的逻辑结构及其存储表示上可以定义不同的运算集合，从而得到不同的数据结构。这样说法对吗？举例说明之。
（957） 评价各种不同数据结构的标准是什么？
（958） 评价一个好的算法，需要从哪几方面来考虑的？
（959） 什么是算法的时间复杂性？
（960） 什么是抽象数据类型？
（961） 数据结构与数据类型有什么区别？
（962） 数据的存储结构由哪四种基本的存储方法实现？
（963） 运算是数据结构的一个重要方面。试举一例，说明两个数据结构的逻辑结构和存储方式完全相同，只是对于运算的定义不同。因而两个结构具有显著不同的特性，是两个不同的结构。
（964） 在编制管理通讯录的程序时, 什么样的数据结构合适? 为什么?
（965） 试举一例，说明对相同的逻辑结构,同一种运算在不同的存储方式下实现，其运算效率不同。
（966） 有实现同一功能的两个算法A1和A2，其中A1的时间复杂度为Tl=O(2n)，A2的时间复杂度为T2=O(n2)，仅就时间复杂度而言，请具体分析这两个算法哪一个好。
（967） 分析下面程序段中循环语句的执行次数。
Int i= 0, s = 0, n = 100;
Do
{
i:=i+1;
s:=s+10*i;
}while ((I<n) && (s<n))
（968） 根据下面程序，回答下面问题：
(1) 试指出f(n)值的大小，并写出f(n) 值的推导过程;
(2) 假定n= 5，试指出f(5)值的大小和执行f(5)时的输出结果。
int f(int n)
{
int i, j, k, sum= 0;
for(i=l; i<n+1; i++)
{
for(j=n; j>i-1; j--)
{
for(k=1; k<j+1; k++ )
{
sum++;
printf("sum=%d\n", sum)；
}
}
}
return (sum);
}
（969） 设n是偶数，试计算运行下列程序段后m的值并给出该程序段的时间复杂度。
int m = 0;
For (int i = 0; i < n; i++)
{
for (int j = 2*i, j < n; j++)
{
m = m + 1;
}
}
（970） 试给出下面两个算法的运算时间。
a. for (int I = 0; I < n; I++)
{
x++;
}
b. for (int I = 1; I < n; I++)
{
for (int j = 1; j < n; j++)
{
x++;
}
}
（971） 快速排序的最大递归深度是多少？最小递归深度是多少？
（972） 对链表设置表头节点的作用是什么？
（973） 有五个数依次进栈：1,2,3,4,5.在各种出栈的序列中，以3,4先出的序列有哪几个。（３在４之前出栈）
（974） 试写出进栈操作，出栈操作算法的时间复杂性。
（975） 已知ＫＭＰ串匹配算法的模式串是AABBAAB,试写出改进后的NEXT信息帧。
（976） 某整型数组Ａ的１０个元素值依次为6,2,9,7,3,8,4,5,0,1,用下列各排序方法，将Ａ中元素由小到大排序。
(1) 取第一个元素值６作为分割数，(2) 试写出快速排序第一次分隔后Ａ中的结果。
(3) 用堆排序，(4) 试写出将第一个选出的数据放在Ａ的最后位置上，(5) 将Ａ调整成堆后的Ａ中结果。
(6) 用基数为３的基数排序法，(7) 试写出第一次分配和收集后Ａ中的结果。
（977） 已知某排序平衡二叉树Ｔ具有下列特点：
(1) 结点的关键字均在1到9范围内；
(2) 在Ｔ中存在一个关键字为n1的叶结点，若删去该结点，立即插入一个关键字为n1的结点，得到的平衡树与原Ｔ不相同；
(３) 在Ｔ中存在另一个关键字为n2的非叶结点，删去它，并立即插入n2结点，得到与原Ｔ相同的平衡树；
(４) 在Ｔ中插入某n3结点后立即删除它，得到的平衡树与原Ｔ不相同。
试画出具有上述特点的最简单（结点个数最少）的平衡树Ｔ，并写明n1,n2,n3分别等于几？
（978） 设一单向链表的头指针为head，链表的记录中包含着整数类型的key域,试设计算法，将此链表的记录按照key递增的次序进行就地排序。
（979） 在排序连续顺序文件中采用折半查找方法查找记录存在与否的过程可以借助于一棵平衡二叉树(也称判定树)来模拟，树中结点的值为记录在文件中的位置序号。
(1) 若文件中有l 9个记录，请画出这棵判定树；
(2) 当文件中有n个记录时，求出该判定树的深度。
（980） 试举例说明用程序设计语言描述堆栈结构时，要涉及那些问题？
（981） 在程序设计语言中实现递归的条件是什么？编写递归子程序，应注意什么？
（982） 动态查找树，有哪几项基本操作？
（983） 举例说明有向图的最短路径算法常用于哪几种情形？
(1) 中断和死锁
(2) 变量与表达式
(3) 对象与属性
(4) 虚拟地址与实地址
(5) 数据的物理结构和逻辑结构
（984） 内存中一片连续空间（不妨假设地址从1到m），提供给两个栈S1和S2使用，怎样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。
（985） 一棵共有n个结点的树，其中所有分枝结点的度均为k，求该树中叶子结点的子数。
（986） 设有一个由正整数组成的无序（向后）单链表，编写完成下列功能的算法：
(1) 找出最小值结点，且打印该数值；
(2) 若该数值是奇数，则将其与直接后继结点的数值交换；
(3) 若该数值是偶数，则将其直接后继结点删除；
（987） 给出下算法的时间复杂度：
main( )
{
int x , n , y ;
scanf("%d", &n);
x=n;
y=0;
while (x >= (y+1)(y+1))
{
y++;
}
}
（988） 试举例说明对相同的逻辑结构，同一种运算在不同的存储方式下实现，其运算效率不同。
（989） 对链表设置表头结点的作用是什么？（至少说出2条好处）
（990） 快速排序在什么情况下排序算法产生恶化，原因是什么？
（991） 设在一个有关串的程序编码当中，有如下定义与赋值：
const char A[] = {'a','b','c','\0'};
char B[] = {'a','b','c','d','\0'};
… …
for (i=0; i<4; i++)
{
A[i] = 'a';
B[i] = 'b';
}
… ...
在该程序编码中是否有错？为什么？
（992） 若A为一下三角矩阵数组，则采用以行为主和以列为主的数据存放方式哪一种更合适？为什么？
（993） 线性表A和B均是按元素值递增有序排列，均以单链表作存储结构。请编写一算法将表A和表B归并成一个按元素值递减有序排列的线性表C（允许表中含有值相同的元素），并要求利用原表空间。
（994） 编写一个算法，对于输入的十进制非负整数，将它的八进制表示打印出来。
（995） 编写函数strcmp(char * s1, char * s2)。若s1和s2均是数字串（包括+/-号），则按照十进制整数大小进行比较；否则按照Ascii序进行比较。s1大于/等于/小于s2时，分别输出1/0/-1。可以直接调用atoi函数。
（996） 请回答下列关于堆（Heap）的一些问题：
(1) 堆的存储表示是顺序的，还是链接的？
(2) 设有一个最小堆，即堆中任意节点的关键码均大于它的左子女和右子女的关键码。其具有最大值的元素可能在什么地方？
(3) 对n个元素进行初始建堆的过程中，最多做多少次数据比较（不用大O表示法）？
（997） 快速排序的时间复杂度是多少？试推导之。
（998） 从键盘上输入一串正整数，以-1为输入结束的标志，试设计一个算法，生成一棵二叉排序树（即依次把该序列中的结点插入二叉排序树）。
（999） 试设计一个算法，在中序线索二叉树中求指定结点P在后序遍历序列中的前驱结点。要求算法为非递归的，空间复杂度为O（1）。
（1000） 修改冒泡排序法以实现双向冒泡排序。即第一次把最大记录放到表尾，第二次将最小记录放到表头，如此反复进行，直至排序结束。试编写此算法。
（1001） 针对以下情况确定非递归的归并排序的运行时间(数据比较次数与移动次数):
(1) 输入的n个数据全部有序;
(2) 输入的n个数据全部逆向有序;
(3) 随机地输入n个数据.
（1002） 说明下列算法的功能：
void a1(stack &s)
{
int i, n, a[255];
n = 0;
while (!stackempty(s))
{
n++;
pos(s, a[n];
}
for (i = 1; i <= n; i++)
{
push(s, a[i]);
}
}
（1003） 说明下列算法的功能：
void a2(stak &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);
}
}
（1004） 说明下列算法的功能：
void change(linklist &head)
{
linklist q, p;
if (head && head->next)
{
q = head;
head = head->next;
p = head;
while (p->next) p = p->next;
p->next = q;
q->next = NULL;
}
}
操作提示