《数据结构(本)》电大期末试题及其答案

《数据结构（本）》期末综合练习题一、单选选择题.栈和队列的共同特点是（C）。A.都是先进先出 B.都是操作受限的线性结构C.都是先进后出 D.元素都可以随机进出.数据的存储结构包括数据元素的表示和（C）。A.数据处理的方法 B.数据元素的类型C.数据元素间的关系的表示 D.相关算法.对一个栈顶指针为top的链栈进行入栈操作，通过指针变量p生成入栈结点，则执行p=（structnode*）malloc（sizeof（structnode）;p->data=a;和（C）。A.top->next=p;p=top; B.p->next=top;p=top;C.p->next=top;top=p; D.top=top->next;p=top;4.树状结构中数据元素的位置之间存在（B）的关系。A.每一个元素都有一个直接前驱和一个直接后继 B.一对多C.一对一 D.多对多5.设头指针为head的非空的单向链表，指针p指向尾结点，则通过以下操作（D）可使其成为单向循环链表。A.head=p; B.p;head;C.p->next=NULL;D.p->next=head;.设有一个长度为26的顺序表，要插入一个元素，并使它成为新表的第6个元素，需移动元素的个数为（D）。A.22B.19C.20D.21.一种逻辑结构（C）。A.与存储该逻辑结构的计算机相关 B.是指某一种数据元素的性质C.可以有不同的存储结构 D.只能有唯一的存储结构.头指针为head的带头结点的单向循环链表，p所指向尾结点，要使该链表成为不带头结点的单向循环链表，可执行head二head->nex;和（A）。A.p->next=head; B.p=head->nextC.head->next=p D.head->next=p->next.把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（D）。A.给数据元素分配存储空间 B.数据元素的存储C.逻辑结构 D.存储结构.元素111，113，115，117按顺序依次进栈，则该栈的不可能输出序列是（D）（进栈出栈可以交替进行）。A. 111， 113， 115， 117 B. 113，111，117，115C. 117， 115， 113， 111 D. 117，115，111，11311.图状结构中数据元素的位置之间存在（B）的关系。A.每一个元素都有一个且只有一个直接前驱和一个直接后继B.多对多C.一对一D.一对一.以下说法正确的是（D）。A.栈和队列的特点都是后进后出 B.队列的特点是先进后出C.栈的特点是先进先出 D.栈的特点是先进后出.一个单链表中，在p所指结点之后插入一个s所指的结点时，可执行：s->next=p->next;和（D）。A.s=p->next; B.p=s->next;C.p->next=s->next; D.p->next=s;.设有一个20阶的对称矩阵A（第一个元素为a1,1），采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵元素a6,2在一维数组B中的下标是（B）。A.28B.17C.21D.23.元素12，14，16，18顺序依次进栈，则该栈的不可能输出序列是（C）。（进栈出栈可以交替进行）。A.18，16，14，12 B. 12，14，16，18C.18，16，12，14 D. 14，12，18，16.设有串p1="ABADF"，P2="ABAFD"，P3="ABADFA"，P4="ABAF"，以下四个串中最大的是（A）。A.p2B.p3C.p4D.p1.设有一个30阶的对称矩阵A（第一个元素为a1,1），采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a9,2在一维数组B中的下标是（A）。A.38B.32C.18D.41.数组a经初始化chara[ ]="English"；a[7]中存放的是（B）。A."h"B.字符串的结束符 C.变量hD.字符h.设有一个长度为32的顺序表，要删除第8个元素需移动元素的个数为（B）。A.15B.24C.22D.14.设主串为“ABcCDABcdEFaBc"，以下模式串能与主串成功匹配的是（B）。A.ABCB.BcdC.AbcD.BCd.在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为（C）。A.2i-1B.2iC.2i+1D.2i+2.在一棵二叉树中，若编号为i的结点存在左孩子，则左孩子的顺序编号为（D）。A.2i+1B.2i-1C.2i+2D.2i.一棵具有16个结点的完全二叉树，共有（B）层。（设根结点在第一层）A.6B.5C.4D.7.如下图所示，若从顶点a出发，按图的广度优先搜索法进行遍历，则可能得到的一种顶点序列为（A）。

A.aecbdfB.aedfcbC.aebcfdD.abecdf.如下图所示，若从顶点a出发，按图的深度优先搜索法进行遍历，则可能得到的一种顶点序列为（C）。A.aebcfgdB.abecdfgC.aedfcgbD.acfebgd.线性表以（B）方式存储，能进行折半查找。A.顺序B.关键字有序的顺序C.二叉树D.链接.字符串“DABcdabcd321ABC”的子串是（C）。A.“321a”B.“aBcd”C.“cd32”D.“ABcD”.一棵具有38个结点的完全二叉树，最后一层有（B）个结点。6B.7C.5D.8.如下图所示，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（C）。A.acbfedgB.abcdfegC.abcdfgeD.abcfgde.下图的拓扑序列是（ ）。A.23645B.56234C.23564D.52346.下面关于线性表的叙述错误的是（D）。A.线性表采用链式存储便于插入和删除操作的实现B.线性表采用链式存储不必占用一片连续的存储空间C.线性表采用顺序存储必须占用一片连续的存储空间D.线性表采用顺序存储便于插入和删除操作的实现.设有头指针为head的不带头结点的非空的单向循环链表，指针p指向其尾结点，要删除第一个结点，则可利用下述语句head=head->next;和（D）。A.p二head; B.head=p; C.p;NULL; D.p->next=head;.以下数据结构中是非线性结构的是（C）。A.线性表B.队列C.二叉树D.栈.以下说法正确的是（B）。A.线性表的链式存储结构必须占用连续的存储空间一种逻辑结构可以有不同的存储结构一种逻辑结构只能有唯一的存储结构D.线性表的顺序存储结构不必占用连续的存储空间.设有一个长度为18的顺序表，要删除第7个元素需移动元素的个数为（B）。A.12B.11C.10D.13.把数据存储到计算机中，并具体体现（A）称为物理结构。A.数据元素间的逻辑关系 B.数据的运算C.数据的处理方法 D.数据的性质.两个字符串相等的充要条件是（B）。A.两个字符串的长度相等 B.同时具备（A）和（C）两个条件C.两个字符串中对应位置上的字符相等 D.以上答案都不对.顺序表所具备的特点之一是（B）。A.删除元素的操作不需要移动元素 B.可以随机访问任一结点C.不需要占用连续的存储空间 D.插入元素的操作不需要移动元素.设某链表中最常用的操作是在链表的尾部插入或删除元素，在已知尾指针的条件下，选用下列（A）存储方式最节省运算时间。A.双向链表B.单向链表 C.单向循环链表 D.双向循环链表.图状结构中数据元素的位置之间存在（A）的关系。A.多对多 B.每一个元素都有一个直接前驱和一个直接后继C.一对多 D.一对一41.元素13，15，19,20顺序依次进栈，则该栈的不可能输出序列是（A）。（进栈出栈可以交替进行）

A.19,13,15,20B.1A.19,13,15,20B.15,13,20,19C.13,15,19,20D.20,19,15,1342.元素20,14,16,18按顺序依次进栈，则该栈的不可能输出序列是（A）。（进栈出栈可以交替进行）A.18,16,20,14B.20,14,16,18C.14,20,18,16D.18,16,14,2043.设指针q指向单链表中结点A,指针p指向单链表中结点A的后继结点B,则在表中删除结点B的操作为（A）。A.q->next=p->next； B.q->next=p；C.p->next=q->next； D.p->next；p=q；.设有一个12阶的对称矩阵A（左上角第一个元素为a1,1）,采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a5,4在一维数组B中的下标是（C）。A.12B.11C.14D.13.栈和队列的共同特点之一是（A）。A.只允许在端点处插入和删除元素 B.都是先进先出C.没有共同点 D.都是先进后出.设有一个长度为22的顺序表，要删除第8个元素需移动元素的个数为（C）。A.25B.15C.14D.23.用链接方式存储的队列，在进行插入运算时（C）。A.头、尾指针都需要修改 B.头、尾指针都不需要修改C.需修改尾指针 D.需修改头指针.在一棵二叉树中，若编号为5的结点存在右孩子，则右孩子的顺序编号为（D）。A.12B.10C.9D.11.字符串a1="AEIJING",a2="AEI",a3="AEFANG",a4="AEFI”中最大的是（D）。A.a2B.a3C.a4D.a1.一棵具有5层的完全二叉树，最后一层有4个结点，则该树总共有（B）个结点。A.18B.19C.15D.14.设有一个20阶的对称矩阵A（第一个元素为a1,1）,采用压缩存储的方式，将其 下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a6,2在一维数组B中的下标是（C）。A.18B.23C.17D.21.如下图所示，若从顶点a出发，按图的广度优先搜索法进行遍历，则可能得到的一种顶点序列为（A）。ggA.abcedfgB.abcfgdeC.acbfedgD.abcdfge.以下说法正确的是（A）。A.二叉树中任意一个非叶结点的值都大于其左子树上所有结点的值，小于其右子树上所有结点的值，则该树为二叉排序树。B.若二叉树中左子树上所有结点的值均小于根结点的值，右子树上所有结点的值均大于根结点的值。则该树为二叉排序树。C.前序遍历二叉排序树可得到一个有序序列。D.二叉树中任意一个结点的值均大于其左孩子的值，小于其右孩子的值。则该树为二叉排序树。.字符串“abcd321ABCD"的子串是（B）。A."321a"B."21ABC"C."abcABCD"D.abcD.二叉树的第k层的结点数最多为（B）。A.2K-1B.2k-1C.2K+1D.2k-1.数组a经初始化chara[]="English"；a[1]中存放的是（D）。A.字符EB."n"C."E"D.字符n.如下图所示，若从顶点6出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（D）。A. 6，2，8，7，9，3，4 B. 6，9，2，3，7，8，4C. 6，2，7，9，8，4，3 D. 6，9，3，2，8，7，4.如下图所示，若从顶点a出发，按图的深度优先搜索法进行遍历，则可能得到的一种顶点序列为（A）。A.aedfcbB.aebcfdC.abecdfD.acfebd59.如下图所示，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为(A)。A.abcdfgeB.abcfegdC.abcfgdeD.acbfedg60.下图的拓扑序列是（B）。A.52346B.52364C.23456D.56423二、填空题.对稀疏矩阵进行压缩存储，可采用三元组表，一个有10行的稀疏矩阵A共有97个零元素，其相应的三元组表共有3个元素。该矩阵A有10列。.结构中的数据元素存在多对多的关系称为图状结构。.在单向链表中，q指向p所指结点的直接后继结点，要删除q所指结点，可以用操作p->next=q->next;。.n个元素进行冒泡法排序，第j趟冒泡要进行n-j次元素间的比较。.对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的行下标、列下标和数组元素_三项信息。.中序遍历二叉排序树可得到一个有序序列。.队列的操作特点是后进后出。.待排序的序列为8,3,4,1,2,5,9,采用直接选择排序算法，当进行了两趟选择后，结果序列为 1,2,4,8,3,5,9 。9皿个元素进行冒泡法排序，通常需要进行n-1 趟冒泡。.广义表((a,b),d,e((i,1),k))的长度是一 4 。.中序遍历二叉排序树可得到一个有序的序列。.广义表的(c,a,(a,b),d,e,((i,j),k))深度是_3_。.广义表(c,a,(a,b),d,e,((i,j),k))的长度是_6_。.对稀疏矩阵进行压缩存储，可采用三元组表，一个有10行10列的稀疏矩阵A共有95个零元素，其相应的三元组表共有 5 个元素。.广义表的（c，a，（a，b），d，e，（（i，j），k））深度是」_。.在对一组记录（50，49，97，22，16，73，65，47，88）进行直接插入排序时，当把第7个记录65插入到有序表时，为寻找插入位置需比也_3_次。.循环队列在规定少用一个存储空间的情况下，队空的判定条件为front==rear。.一棵有5个叶结点的哈夫曼树，该树中总共有9个结点。.c语言中，字符串“E”存储时占_2一个字节。.设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有 12个结点。（根所在结点为第1层）。.一棵二叉树中有n个非叶结点，每一个非叶结点的度数都为2,则该树共有一n±L个叶结点。.设有一个长度为40的顺序表，要删除第8个元素需移动元素的个数为 32 。.在对一组记录（55，39，97，22，16，73，65，47，88）进行直接插入排序时，当把第7个记录65插入到有序表时，为寻找插入位置需比也_3_次。.有以下程序段：chara[]="English”;char*p=a;intn=0;while（*p!='\0’）{n++;p++;}结果中，n的值是7 。.设：chara[]="AEJING";该字符串在计算机中存储时占 8个字节。.栈的特点之一是：元素进、出栈的次序是：先进 后出。.结构中的数据元素存在多对多的关系称为 图状结构。.对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的三项信息是行下标，列下标，数组元素 。.对稀疏矩阵进行压缩存储，可采用三元组表,一个有8行的稀疏矩阵A共有92个零元素，其相应的三元组表共有4个元素。该矩阵A有，列。.在对10个记录的序列（9,35，19,77,2，10，53,45,27,68）进行直接插入排序时,当把第6个记录10插入到有序表时，为寻找插入位置，元素间需比较4次。（按升序排序）.循环链队列中，设front和rear分别为队头和队尾指针，最大存储空间元素为MaxSize,采用少用一个存储空间的模式，则判断循环链队列为空的条件是front==rear为真。.字符串a1="beijing",a2="bef",a3="beifang",a4="befi"最小的是__a2^_。.n个元素进行冒泡法排序，第j趟冒泡要进行 n-j 次元素间的比较。.10个元素进行冒泡法排序，其中第5趟冒泡共需要进行_5_次元素间的比较。.设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有 12个结点。（根所在结点为第1层）.中序遍历一棵二叉排序树可得到一个有序序列.中序遍历一棵二叉排序树树可得到一个有序序列。TOC\o"1-5"\h\z.广义表（c,（a,b,c）,（d,e,f）,（（i,1）,女））的长度是4 。.待排序的序列为9,4,5,1,2,6,10,采用直接选择排序算法，当进行了两趟选择后,结果序列为。.广义表的（c,（b,a,b）,f,e,（（i,1）,女））深度是 3 。.广义表（（a,b）,d,e,（（i,1）,k））的长度是4 。.序列4,2,5,3,8,6,采用冒泡排序算法（升序），经一趟冒泡后，结果序列是2,4,3,5,6,8 。.广义表的（c,a,（a,b）,d,e,（（i,j）,k））深度是_3_。.待排序的序列为8,3,4,1,2,5,9,采用直接选择排序算法，当进行了两趟选择后，结果序列为1,2,4,8,3,5,9 。.线性表用顺序方式存储需要占用连续的存储空间。.线性表用顺序 方式存储可以随机访问。.线性表用关键字有序 的顺序方式存储，可以用二分法排序。.顺序表6,5,1,2,4,3,8,7经过一趟（1,1）归并后的结果序列为 （5,6）,（1,2）,（3,4）,（7,8） 。三、综合题.有一个长度为11的有序表（1,2,11,15,24,28,30,56,69,70,80）,元素的下标依次为：1,2,3,……，11,按折半查找对该表进行查找。（1）画出对上述查找表进行折半查找所对应的判定树。（2）说出成功查找到元素56,需要依次经过与哪些元素的比较？（3）说出不成功查找元素72,需要进行元素比较的次数？（2）28,69,30,56（3）4次.（1）以3,4,5,8,9,作为叶结点的权，构造一棵哈夫曼树。（2）给出相应权重值叶结点的哈夫曼编码。（3）n个叶结点的哈夫曼树，总共有多少个结点？⑴答：（2）答：3:000 4:001 5:01 8:10 9:11⑶2n-13.（1）一组记录的关键字序列为（57,90,67,50,51,56）,利用堆排序（堆顶元素是最小元素）的方法建立初始堆（要求以完全二叉树描述）。（2）对关键字序列（56,51,71,54,46,106）利用快速排序，以第一个关键字为分割元素，给出经过一次划分后结果。（3）一组记录的关键字序列为（60,47,80,57,39,41,46,30）,利用归并排序的方法，分别给出（1,1）归并、（2,2）归并、（4,4）归并的结果序列。⑴答：46,51,54,56,71,106（47,60） （57,80） （39,41） （30,46）（47,57,60,80） （30,39,41,46）（30,39,41,46,47,57,60,80）4.（1）设有数据集合{40,29,7,73,101,4,55,2,81,92,39},依次取集合中各数据构造一棵二叉排序树。（2）在上述二叉排序树上进行查找，给出成功查找到元素92的查找路径，其中共经过了多少次元素间的的比较。（3）有一个长度为10的有序表，按折半查找对该表进行查找，给出在等概率情况下查找成功的平均比较次数为。（1）-3CDCD®CD40,73,101,81,92。共5个元素比较。29/105.（1）以2,3，4，7，8，9作为叶结点的权，构造（2）给出相应权重值叶结点的哈夫曼编码。（3）一组记录的关键字序列为（47，80，57，39，41始堆（堆顶元素是最小元素，以树的形式给出）。CDCD2：00003：00014：0017：10€一棵哈夫曼树。，46），利用堆排序的方法建立的初8：119:01(3)6.（1）一组记录的关键字序列为（36,69,46,28,30,35）,给出利用堆排序（堆顶元素是最小元素）的方法建立的初始堆（要求以完全二叉树描述）。（2）对关键字序列（36,69,46,28,30,74）采用快速排序，给出以第一个关键字为分割元素，经过一次划分后的结果。（3）设有数据集合{30,73,101,4,8,9,2,81},依次取集合中各数据构造一棵二叉排序树。答：（1）28,30,35,69,36,46(2)30,28,36,46,69,74（3）7.（1）已知某二叉树的后序遍历序列是debca,中序遍历序列是dbeac,试画出该二叉树。（2）若上述二叉树的各个结点的字符分别代表不同的整数（其中没有相等的），并恰好使该树成为一棵二叉排序树，试给出a、b、c、d、e的大小关系。（3）给出该树的前序遍历序列。(1)d<b<e<a<cabdec(1)一组记录的关键字序列为｛45,40,65,43,35,95｝,写出利用快速排序的方法，以第一个记录为基准得到的一趟划分的结果(要求给出一趟划分中每次扫描和交换的结果)。(2)对序列｛45,40,65,43,35,95｝利用直接插入排序，写出逐次插入过程(从第一个元素一直到第六个元素)。度]406543359535406543国953540[|j]436595354043期6595354043画6595TOC\o"1-5"\h\z40 45 65 43 35 9540 43 45 65 35 9535 40 43 45 65 95(1)设head1和p1分别是不带头结点的单向链表A的头指针和尾指针，head2和p2分别是不带头结点的单向链表B的头指针和尾指针，若要把B链表接到A链表之后，得到一个以head1为头指针的单向循环链表，写出其中两个关键的赋值语句(不用完整程序，结点的链域为next)。(2)单向链表的链域为next,设指针p指向单向链表中的某个结点，指针s指向一个要插入链表的新结点，现要把s所指结点插入p所指结点之后，某学生采用以下语句：p->next=s;s->next=p->next;这样做正确吗？若正确则回答正确，若不正确则说明应如何改写。答：(1)p1->next=head2；p2->next=head1；(2)不对，s->next=p->next；p->next=s；(1)设根为第1层，对给定权值1,3,4,4,5,6,构造深度为5的哈夫曼树。提示：构造中当出现被选的结点值有多个相等时，可尝试不同组合，以得到要求的树的深度。(2)求树的带权路径长度。(3)用链接法存储上述哈夫曼树，结点中共有多少个指针域为空，说明理由？(4)给出对上述哈夫曼树中序遍历得到的的序列。(5)一棵哈夫曼树有n个非叶结点，构造该树共有多少个权重值？简述理由？答：⑴(2)WPL=1*4+3*4+4*3+6*2+4*2+5*2=58(3)有12个空指针域，因为共11个结点，22个指针域，除根结点外，每个结点对应一个指针域，共10个指域非空，故有22-10=12个空指针域。(针对哈夫曼树还可有其它理由)(4)1，4，3，8，4，14，6，23，4，9，5(5)n+1,因为叶结点比非叶结点多1。四、程序填空1.以下是中序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点)。voidInorder(structBTreeNode*BT){if(BT!:NULL)Inorder(BT->left)；printf("%c",BT->data)；Inorder(BT->right);}利用上述程序对下图进行遍历，结果是(3)dbfeac。2.设线性表为(16,20,26,24)，以不带头结点的单向链表存储，链表头指针为head，以下程序的功能是输出链表中各结点中的数据域data。structnode{intdata;structnode*next;};typedefstructnodeNODE;#defineNULL0voidmain(){NODE*head,*p;p=head;/*p为工作指针*/doTOC\o"1-5"\h\z{printf("%d\n",(1) );⑵ ；}while((3) );}答：(1)p->data⑵p=p->next(3)p!=NULL3.以下冒泡法程序对存放在a[1],a[2],……，a[n]中的序列进行排序，完成程序中的空格部分，其中n是元素个数，要求按升序排列。voidbsort(NODEa[],intn){NODEtemp;inti,j,flag;for(j=1;⑴ ；j++){flag=0;for(i=1;(2) ;i++)if(a[i].key>a[i+1].key){flag=1;temp=a[i];⑶ ：(4);}if(flag==0)break;}}设有序列6,4,5,8,2，1，给出由该程序经过两趟冒泡后的结果序列(5)。答：⑴j<=n-1(2)i<=n-j(3)a[i]=a[i+1](4)a[i+1]=temp(5)4，5，2，1，6，84.以下函数为直接选择排序算法，对a[1]，a[2]，……，a[n]中的记录进行直接选择排序，完成程序中的空格：typedefstruct{intkey;}NODE;voidselsort(NODEa[],intn){inti,j,k；NODEtemp;TOC\o"1-5"\h\zfor(i=1;i<= (1) ;i++){k=i；for(j/i+1;j<= (2) ;j++)if(a[j].key<a[k].key)(3) ;if(i!=k){temp=a[i];(4);(5);}}}答：⑴n-1nk=ja[i]=a[k]a[k]=temp5.设线性表为(1,3,7,5)，以下程序用说明结构变量的方法建立单向链表，并输出链表中各结点中的数据。structnode{intdata;structnode*next;}typedefstructnodeNODE;#defineNULL0Voidmain(){NODEa,b,c,d,*head,*p;a.data=6;b.data=10;c.data=16;c.data=4; /*d是尾结点*/head= (1) ;a.next;&b;b.next;&c;c.next;&d;(2) ； /*以上结束建表过程*/p二head; /*p为工作指针，准备输出链表*/do{

printf（"%d\n",（3） ）;（4）;}while（p!:NULL）;}画出按该程序建立的单向链表的示意图，说明程序运行结束后口的指向。 （5）答：（1）&ad->next=NULLp->datap=p->next（5）P指向NULL61016—►4NULLhead 6.以下函数在a[0]到a[n-1]中，用折半查找算法查找关键字等于k的记录，查找成功返回该记录的下标，失败时返回-1，完成程序中的空格：typedefstruct{intkey;}NODE;intBinary_Search（NODEa[],intn,intk）{intlow,mid,high;low=0;high=n-1;TOC\o"1-5"\h\zwhile（（1） ）{mid=（low+high）/2;if（a[mid].key==k）return（2） ;elseif（ （3） ）low=mid+1;else（4） ;}return-1;}设数组元素：a[0]=2；a[1]=5；a[2]=3；a[3]=4；a[4]=9；a[5]=6；a[6]=1；a[7]=10；按上述程序查找元素5，能否成功查到，说明理由 （5）。答：（1）low<=high（2）mid（3）a[mid].key<k（4）high=mid-1（5）不能，因为不是有序序列，不能用折半查找。7.以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中左、右指针域分别为left和right,数据域data为字符型，BT指向根结点)。voidInorder(structBTreeNode*BT){if(BT!:NULL){⑴ ；Inorder(BT->right);⑵ ；}}利用上述程序对下图进行遍历，结果是(3)。答：（1）Inorder（BT->left）（2）printf（"%c”,BT->data）（3）f,d,e,b,c,a8.以下函数为链队列的入队操作，x为要入队的结点的数据域的值，front、rear分别是链队列的队头、队尾指针structnode{ElemTypedata;structnode*next;};structnode*front,*rear;voidInQueue（ElemTypex）{structnode*p;TOC\o"1-5"\h\zp=（structnode*）（1） :p->data=x;p->next=NULL;⑵ ；rear= （3） ;答：⑴malloc（sizeof（structnode））（2）rear->next=p⑶p9.设有一个头指针为head的不带头结点单向链表，p、q是指向链表中结点类型的指针变量，p指向链表中某结点a（设链表中没有结点的数据域与结点a的数据域相同），写出相关语句：（1）使该单向链表成为单向循环链表；（2）删去a结点q=p;x=p->data;while（q->next!=NULL）q=q->next;⑴ ；q=p;p=p->next;while（p->data!=x）{q=p;⑵ ；}（3）;答：（1）q->next=headp=p->nextq->next=p->next模拟练习题（一）一、单项选择题（每小题2分，共30分）1、单向链表所具备的特点是（C）。A.可以随机访问任一结点B.占用连续的存储空间C.插入删除不需要移动元素 D.可以通过某结点的指针域访问其前驱结点2、设有一个长度为18的顺序表，要在第6个元素之前插入一个元素（也就是插入元素作为新表的第6个元素），则移动元素个数为（A）。A.13B.5C.12D.63、栈和队列的共同特点是（C）。A.都是先进后出 B.都是先进先出 C.都是线性结构 D.元素都可以随机进出4、元素1,3,5,7按顺序依次入队列，按该队列的出队序列进栈，该栈的可能输出序列是（B ）（进栈出栈可以交替进行）。A.5，1，3，7B.7，5，3，1C.7，5，1，3D.7，3，1，55、在一个不带头结点的链队中，假设f和r分别为队头和队尾指针，则对该队列进行出队操作中并把结点的值保存在变量e中，其运算为e=f-data；和（ C）。A.f-next=f; B.r=r-next;C.f=ffnext;D.r-next二r;6、设有一个对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），B数组共有45个元素，则该矩阵是（B）阶的对称矩阵。A.11B.9C.15D.107、下列是C语言中"abcd321ABCD”的子串的选项是（B）。A.abcDB."21ABC"C."abcABCD"D."321a"8、字符串a1="BEIJING"，a2="BEF"，a3="BEFANG"，a4="BEFI"最小的是（D）。A.a1 B. a3 C. a4 D.a29、一棵有20个结点采用链式存储的二叉树中，共有（D ）个指针域为空。A.18 B. 19 C. 20 D.21）个非叶结点。10、设一棵哈夫曼树共有18个叶结点，则该树有（C）个非叶结点。A.16B.19C.17D.1811、如下图所示的一个图，若从顶点g出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（C）。A.gaebcfdB.gabecdfC.gaedfcbD.gacfebd12、线性表以（C ）方式存储，能进行折半查找。A.顺序B.链接C.关键字有序的顺序 D.关键字有序的13、有一个长度为8的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（D）。A.22/8B.20/8C.23/8D.21/814、排序算法中，从尚未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行比较（要求比较次数尽量少），然后将其放入已排序序列的正确位置的方法是（ C）。A.归并排序B.选择排序C.折半插入排序 D.直接插入排序15、排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始为空）的一端的方法，称为（B）排序。A.快速B.选择C.冒泡D.堆二、填空题（每小题2分，共24分）16、广义表（a，（a，b），d，e，（（i，j），k））的长度是 5 。17、广义表的（c，a，（a，b），d，e，（（i，j），卜））深度是3 。18、设顺序队列的类型为typedefstructElemTypedata[MaxSise];intfront,rear;}Squeue;Squeue*sq;sq为指向顺序队列的指针变量，要进行新元素x的入队操作，按教课书约定，可用语句sq->data[sq->rear]=x;和sq->rear++。19、序列4,2,5,3,8,6,采用冒泡排序算法，经一趟冒泡后，序列的结果是2.Q。（按由小到大顺序）20、在对一组记录（50，34，92，19，11，68，56,41，79）进行直接插入排序（由小到大排序），当把第7个记录56插入到有序表时，为寻找插入位置需比较3次。21、数据结构中，数据元素可以由一个或多个数据项组成。22、循环队列中，设front和rear分别为队头和队尾指针，（最多元素为MaxSize,采用少用一个元素的模式），判断循环队列为满的条件为front==（rear+1）%MaxSize为真。23、排序算法中，从尚未排序序列中依次取出元素与已排序序列（初始为空）中的元素依次进行比较，然后将其放入已排序序列的正确位置的方法是直接插入排序。24、对稀疏矩阵进行压缩存储，可采用三元组表，一个6行7列的稀疏矩阵A共有34个零元素，其相应的三元组表共有_8_个元素。25、在双向链表中，要删除p所指的结点，可以先用语句（p-〉prior）-〉next=p-〉next；然后再用语句（p-〉next）-〉prior;p->prior;。26、在双向链表中，每个结点有两个指针域，一个指向结点的直接后继，另一个指向_结点的直接前驱。27、把数据存储到计算机中，并具体体现数据之间的逻辑结构称为存储结构。三、综合题（每小题15分，共30分）28、设数据集合a二{1,12,5,8,3,10,7,13,9}（1）依次取a中各数据，构造一棵二叉排序树。（2）说明如何依据此二叉树得到a的有序序列。（3）对该二叉树进行查找，成功查找到7要进行多少次元素间的比较？（4）给出对该二叉树后序遍历的序列。（5）画出在二叉树中删除12后的树结构（要求结点13的位置不变）。

11答：⑴(2)中序遍历1,3,5,7,8,9,10,12,135次3,7,9,10,8,5,13,12,1(5)29、设有序表为(2,5,129、设有序表为(2,5,11,12,30,4858,70,78,79,90）,元素的序号依次为1,2,32,3,,11。（1）画出对上述查找表进行折半查找所对应的判定树（树中结点用序号表示）（2）说明成功查找到元素2需要经过多少次比较?（3）说明不成功查找元素75需要经过多少次比较?（4）给出后序遍历该折半查找判定树的序列（5）给出中序遍历该折半查找判定树的序列3次（3）4次（4）2，1，5，4，3，8，7，11，10，9，6（序号）（5）1，2，3，4，5，6，7，8，9，10，11（序号）四、程序填空题（每空2分，共16分）30、设有一个不带头结点的单向链表，头指针为head，p、prep是指向结点类型的指针，该链表在输入信息时不慎把相邻两个结点的信息重复输入，以下程序段是在该单向链表中查找这相邻两个结点，把该结点的数据域data打印出来，并把其中之一从链表中删除，填写程序中的空格。prep二head;p=prep->next;while(p->data!二prep->data)prep二p;}printf(“min=%d”，(2));prep->next;(3)答：（1）p=p->next;⑵p->data或prep->datap->next31、以下程序是折半插入排序的算法（按记录中关键字key排序）设待排序的记录序列存放在a[1],…，a[n]中，以a[0]作为辅助工作单元，以下程序是要把a[i]插入到已经有序的序列a[1]，…，a[i-1]中。voidbinsort（NODEa[],intn）{intx,i,j,s,k,m;for（i=2；i<=（1）;i++）{a[0]=a[i];x=a[i].key;s=1;j=i-1;while（s<=j）{m=（2）;if（x<a[m].key）（3）;else}for（k=i-1;k>=j+1;k ）=a[k];a[j+1]=a[0];}}答：⑴n（s+j）/2j=m-1s=m+1（5）a[k+1]

模拟练习题（二）一、单项选择题（每小题2分，共30分）1、头指针为head的带头结点的单向链表为空的判定条件是（C）为真。A.head->next!二NULL B.head==NULLC.head->next==NULL D.head->next=NULL;2、设有一个长度为32的顺序表，要删除第8个元素需移动元素的个数为（B）。A.9B.24C.25D.83、一个栈的进栈序列是2,4,6,8,10,则栈的不可能输出序列是（A）（进栈出栈可以交替进行）。A.8，6，10，2，4 B.8，10，6，4，2C.10，8，6，4，2 D.2，4，6，8，104、一个队列的入队序列是a，b，c，d，按该队列的可能输出序列使各元素依次入栈，该栈的可能输出序列是（C）。（进栈出栈可以交替进行）。A.d，a，b，cB.c，a，b，dC.d，c，b，aD.d，b，a，c5、在一个链队中，假设f和r分别为队头和队尾指针，p指向一个已生成的结点，现要为该结点的数据域赋值e，并使结点入队的运算为p->data=e;p->next=NULL/（（D）。A.f->next=p;f=p;B.p->next=f;f=p;C.p->next=r;r=p;D.r->next=p;r=p;6、设有一个24阶的对称矩阵A，采用压缩存储的方式（矩阵的第一个元素为雪），将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则数组中第30号元素对应于矩阵中的元素是（C）。A",8 B.a8,5 0”,2 D-'27、字符串a1="BEIJING"，a2="BEI"，a3="BEFANG"，a4="BEFI”中最大的是（C）。A.a3B.a4C.a1D.a2

A.a3B.a4C.a1D.a28、程序段chara[]=“English”;char*p=a;intn=0;while（*p!:‘\0’）｛n++;p++;｝结果中，n的值是（D）。A.5B.6C.8D.79、在一棵二叉树中，若编号为5的结点存在左孩子，则左孩子的顺序编号为（D）。A.9B.11C.12D.1010、设一棵采用链式存储的二叉树，除叶结点外每个结点度数都为2,该树结点中共有20个指针域为空。则该树有（ A ）个叶结点。A.10B.9C.22D.2111、已知如下图所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（A）。A.abcefdgB.acfdebgC.abcedfgD.aebcfdg12、在有序表｛10，23，32，36，53，66，68，76，87，90，101，120｝中，用折半查找值53时，经（D）次比较后查找成功。A.8B.6C.3D.413、有一个长度为11的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（C）。A.26/11B.29/11C.33/11D.30/1114、设已有口个元素有序，在未排好序的序列中挑选第m+1个元素，并且只经过一次元素的交换就使第m+1个元素排序到位，该方法是（D）。A.归并排序B.快速排序C.堆排序D.简单选择排序15、一组记录的关键字序列为（32,65,42,24,26,80），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（A）。A.A.26,24,32,42,65,80B.26,24,32,65,42,80C.24,26,32,42,65,80D.26,24,32,80,42,65二、填空题(每小题2分，共24分)16、结构中的数据元素存在一对多的关系称为结构。17、栈的操作特点是后进先出 。18、广义表的(a,(a,b),d,e,((i,j),k))深度是__3_。19、广义表((a,b),d,e,((i,j),k))的长度是—4—。20、设顺序队列的类型为typedefstruct{ElemTypedata[MaxSise];intfront,rear;}Squeue;Squeue*sq;sq为指向顺序队列的指针变量，要进行元素的出队操作，并把元素赋给边量x,按教科书约定，可用语句x=sq—〉data「sq—〉front]/Dsq->fronf++:。21、设顺序队列的类型为typedefstruct{ElemTypedata[MaxSise];intfront,rear;}Squeue;Squeue*sq;sq为指向顺序队列的