2024年高等教育工学类自考-02331数据结构笔试参考题库含答案

“人人文库”水印下载源文件后可一键去除，请放心下载！（图片大小可任意调节）2024年高等教育工学类自考-02331数据结构笔试参考题库含答案“人人文库”水印下载源文件后可一键去除，请放心下载！第1卷一.参考题库(共75题)1.与单链表相比，双链表的优点之一是（）。A、插入、删除操作更简单B、可以进行随机访问C、可以省略表头指针或表尾指针D、顺序访问相邻结点更灵活2.已知关键序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后得到的小根堆是（）A、3，5，12，8，28，20，15，22，19B、3，5，12，19，20，15，22，8，28C、3，8，12，5，20，15，22，28，19D、3，12，5，8，28，20，15，22，193.什么叫二维数组的行序优先存储？什么叫二维数组的列序优先存储？4.有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的（）。5.数据结构被形式地定义为（D，R），其中D是（）的有限集合，R是D上的（）有限集合。6.已知一个有序表为（12，18，24，35，47，50，62，83，90，115，134），当折半查找值为90的元素时，经过（）次比较后查找成功。A、2B、3C、4D、57.一个双向栈S是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端。试为此双向栈设计初始化InitStack（S）、入栈Push（S，i，x）和出栈Pop（S，i）等算法，其中i为0或1，用以表示栈号。8.下列排序算法中，（）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。A、堆排序B、冒泡排序C、快速排序D、插入排序9.链栈与顺序栈相比有一个明显的优点，即（）A、插入操作更加方便B、通常不会出现栈满的情况C、不会出现栈空的情况D、删除操作更加方便10.一个广义表的深度是指该广义表展开后所含括号的层数。11.设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉中共有（）个结点。A、2nB、n+lC、2n-1D、2n+l12.设按低下标优先存储整数数组A[9][3][5][8]时，第一个元素的字节地址是100，每个整数占4个字节，a[3][1][2][5]的存储地址是（）。13.定义字符数组正确的是（）。A、chars[]="Student"；B、chars[7]="Student"；C、chars[7]={’S’，’t’，’u’，’d’，’e’，’n’，’t’}；D、chars[]={"Student"}；14.向一个栈顶指针为top的链式栈中插入一个新结点*p时，应执行（）和（）操作。15.如果只想得到一个序列中第k个最小元素之前的部分排序序列，最好采用什么排序方法？为什么？对于序列{57，40，38，11，13，34，48，75，25，6，19，9，7}，得到其第4个最小元素之前的部分序列{6，7，9，11}，使用所选择的排序算法时，要执行多少次比较？16.设栈的输入序列是（1、2、3、4），则（）不可能是其出栈序列。A、1243B、2134C、1432D、4312E、321417.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（）A、2hB、2h-1C、2h+1D、h+118.在所有结点的权都相等的情况下，只有最下面两层结点的度数可以小于2，其他结点的度数必须等于2的二叉排序树才是最佳二叉树。19.当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。20.单链表中删除p指针指向结点的后继（假设存在）的时间复杂度是（）。A、O（1）B、O（n）C、O（nn）D、以上都不对21.什么是算法的渐近时间复杂度？如何分析一个算法的渐近时间复杂度？22.设无向图G（如图所示），给出该图的最小生成树上边的集合并计算最小生成树各边上的权值之和。 23.设有串S1=’Ianastudent’,S2=’st’,其index(S1,S2)=（）24.假定用于通信的电文由8个字符A、B、C、D、E、F、G、H组成，各字母在电文中出现的概率为5％、25％、4％、7％、9％、12％、30％、8％，试为这8个字母设计哈夫曼编码。25.数据的（）包括查找、插入、删除、更新、排序等操作类型。A、逻辑结构B、存储结构C、算法描述D、基本运算26.（）结构中，数据元素间存在一对多的关系。27.对线性表进行折半查找时，要求线性表必须（）。A、以顺序方式存储B、以顺序方式存储，且结点按关键字有序排列C、以链式方式存储D、以链式方式存储，且结点按关键字有序排列28.对比顺序表与单链表，说明顺序表与单链表的主要优点和主要缺点。29.既希望查找速度快又便于线性表动态变化的查找方法有（）A、顺序查找B、折半查找C、索引顺序查找D、哈希法查找30.指出下述程序段的功能是什么？ 31.简述在顺序栈的栈顶插入一个元素的操作过程。32.二叉排序树中左子树上所有结点的值均（）根结点的值。A、C、=D、!=33.栈的使用非常广泛，在进制转换、括号匹配、表达式求值等算法都能用到。34.在无向图中定义顶点vi与vj之间的路径为从vi到vj的一个（）。A、顶点序列B、边序列C、权值总和D、边的条数35.设一哈希表表长M为100，用除留余数法构造哈希函数，即H（K）=KMODP（P<=M），为使函数具有较好性能，P应选（）36.带头结点head的双循环链表为空表的条件是（）或（）37.在双向循环链表中，在p指针所指的结点后插入一个指针q所指向的新结点，修改指针的操作是（）。A、p->next=q；q->prior=p；p->next->prior=q；q->next=q；B、p->next=q；p->next->prior=q；q->prior=p；q->next=p->next；C、q->prior=p；q->next=p->next；p->next->prior=q；p->next=q；D、q->next=p->next；q->prior=p；p->next=q；p->next=q；38.冒泡排序算法关键字比较的次数与记录的初始排列次序无关39.线索二叉链表是利用（）域存储后继结点的地址。A、lchildB、dataC、rchildD、root40.已知如图所示的无向网，请给出： ①邻接矩阵； ②邻接表；  ③最小生成树。 41.凡能被计算机存储、加工的对象通称为（）42.设head为单循环链表L的头结点，则L为空表的条件是（）43.顺序存储结构的特点是（），链接存储结构的特点是（）。44.设计算法判定一棵二叉树是否为二叉排序树。45.数据结构里，算法的特性包含输入、输出、有穷性、（）和可行性。A、确定性B、二义性C、多变性D、模糊性46.对具有n个元素的有序表采用二分查找法，则算法的时间复杂性为（）A、O（n）B、O（n2）C、O（1）D、O（log2n）47.执行下面程序段时，执行S语句的次数为（） A、n2B、n2/2C、n（n+1）D、n（n+1）/248.关于字符串描述正确的是（）。A、字符串可以为空串B、字符串的长度计算’/0’在内C、字符串比较函数strcmp返回值类型是charD、字符串求长度使用strcat49.散列技术的查找效率主要取决于散列函数和处理冲突的方法。50.在一棵树中，（）结点没有前驱结点，其余每个结点有且只有一个（），可以有任意多个（）结点。51.非空左斜树的先序遍历序列和后序遍历序列正好相反。52.在一个表头指针为ph的单链表中，若要向表头插入一个由指针p指向的结点，则应执行（）操作。A、ph=p；p-＞next=phB、p-＞next=Ph；p=phC、p-＞next=ph-＞next；ph=pD、p-＞next=ph-＞next；ph-＞next=p53.下列选项中关于栈的删除操作描述正确的是（）。A、栈的删除操作叫做出栈B、栈的删除操作叫做弹栈C、栈的删除操作叫做压栈D、栈的删除操作叫做进栈54.链式存储的线性表可以随机存取55.已知一组待排序的记录关键字初始排列如下：45，34，87，25，67，43，11，66，27，78 。（）是初始堆（大堆顶）。A、27，34，11，25，45，43，87，66，67，78B、87，78，45，66，67，43，11，25，27，34C、11，43，34，25，45，66，27，67，87，78D、11，43，34，45，25，66，87，67，27，78E、34，45，25，67，43，11，66，27，78，87F、87，45，11，25，34，78，27，66，67，43G、27，34，11，25，43，45，67，66，87，78H、34，11，27，25，43，78，45，67，66，8756.在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从（）进行查找任何一个元素。57.如果想在4092个数据中只需要选择其中最小的5个，采用（）方法最好。A、起泡排序B、堆排序C、锦标赛排序D、快速排序58.计算机算法指的是（）A、计算方法B、调度方法C、排序方法D、解决某一问题的有限运算序列59.排序方法中，从无序序列中选择关键字最小的记录，将其与无序区（初始为空）的第一个记录交换的排序方法，称为（）。A、希尔排序B、归并排序C、插入排序D、选择排序60.线性结构的基本特征是：每个元素有且仅有一个直接前驱和一个直接后继。61.广义表运算式HEAD（TAIL（（a，b，c），（x，y，z）））的结果是：（）。62.当待排序的元素很多时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂性的主要因素。63.在单链表中设置头结点的作用是（）。64.假定一个待散列存储的线性表为（32，75，29，63，48，94，25，46，18，70），散列地址空间为HT[13]，若采用除留余数法构造散列函数和线性探查法处理冲突，试求出每一元素的散列地址，画出最后得到的散列表，求出平均查找长度。65.在等概率情况下，一棵平衡树的ASL为（）A、O（1）B、O（log2n ）C、O（（log2n）2）D、O（nlog2n）66.设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（）方法可以达到此目的。A、快速排序B、堆排序C、归并排序D、插入排序67.当一个线性表经常进行存取操作而很少进行插入和删除操作时，则采用（）存储结构为宜，相反，当经常进行的是插入和删除操作时，则采用（）存储结构为宜。68.的深度是（）69.对特殊矩阵采用压缩存储的目的主要是为了（）A、表达变得简单B、对矩阵元素的存取变得简单C、去掉矩阵中的多余元素D、减少不必要的存储空间70.设高度为h的二叉数上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（）A、2hB、2h-1C、2h+1D、h+171.假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同的元素）排列的线性表C，并要求利用原表（即A表和B表）的结点空间构造C表。72.对于两棵具有相同记录集合而具有不同形态的二叉搜索树，按中序遍历得到的结点序列是相同的。73.数据结构里，实参和形参的关系（）。A、实参传给形参B、实参的类型要与形参一致C、实参的个数要与实参一致D、实参的名称要与形参的一致74.设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（）A、n，eB、e，nC、2n，eD、n，2e75.表达式求值是（）应用的一个典型例子。第2卷一.参考题库(共75题)1.设哈希（散列）表表长为15（哈希地址为0~14），哈希函数为H（key）=key%11，冲突处理采用线性探测Hi=（H（key）+1）%11，则将一列数15，20，26，30，35，40存储该哈希表，元素40的哈希地址为（）2.可由一个尾指针唯一确定的链表有（）、（）、（）。3.下列排序算法中（）不能保证每趟排序至少能将一个元素放到其最终的位置上。A、快速排序B、shell排序C、堆排序D、冒泡排序4.数据结构里，以下是算法的特性是（）。A、有穷性B、数据C、其它D、以上都不对5.中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。6.某二叉树的中序遍历序列为：DEBAC，后序遍历序列为：EBCAD。则前序遍历序列为（）。7.设哈希函数H（K）=3 K mod 11，哈希地址空间为0～10，对关键字序列（32，13，49，24，38，21，4，12），按下述两种解决冲突的方法构造哈希表，并分别求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和ASLunsucc。  ① 线性探测法；  ② 链地址法。8.字符串“abcd321ABCD”的子串是（）。A、“21ABC”B、“abcABCD”C、abcDD、“321a”9.假定利用数组a[m]顺序存储一个栈，用top表示栈顶指针，用top==0表示栈满，该数组所能存储的栈的最大长度为m，当（）时，再做退栈运算会发生“下溢”。A、top == m-1B、top == 0C、top == mD、top == 110.在对n个元素进行起泡排序的过程中，最好情况下的时间复杂度为：（）A、.O（n3）B、O（n2）C、O（n）D、O（1）11.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当入队一个元素，再出队两个元素后，rear和front的值分别为：（）A、 1和5B、 2和4C、 4和2D、 5和112.图的（）优先搜索遍历算法是一种递归算法，图的（）优先搜索遍历算法需要使用队列。13.数据结构里，算法的输出可以是1到N个，意味着算法必须有输出。14.一个子串在包含它的主串中的位置是指（）。A、子串的最后那个字符在主串中的位置B、子串的最后那个字符在主串中首次出现的位置C、子串的第一个字符在主串中的位置D、子串的第一个字符在主串中首次出现的位置15.设有一个长度为35的顺序表，要在第5个元素之前插入1个元素（也就是插入元素作为新表的第5个元素），则移动元素个数为（）A、30B、31C、5D、616.设有数据结构（D，R），其中D={1，2，3，4，5，6}，R={（1，2），（2，3），（2，4），（3，4），（3，5），（3，6），（4，5），（4，6）}。试画出其逻辑结构图并指出属于何种结构。17.数据结构里，下面关于字符数组描述正确的是（）A、gets（）读取的字符串，其长度没有限制，以敲回车键结束。B、puts（）函数，该函数一次只能输出一个字符串C、strcmp（）函数，字符串1小于字符串2，函数返回值整数-1D、strcpy（）函数功能是进行字符串连接.18.不是数据的逻辑结构是（）A、散列结构B、线性结构C、树结构D、图结构19.在一棵具有5层的满二叉树中结点总数为（）。A、31B、32C、33D、1620.顺序查找时间为O（n），二分查找时间为O（log2n），散列查找时间为O（1），为什么有高效率的查找方法而不放弃低效率的方法？21.将二叉排序树T按前序遍历序列依次插入初始为空的二叉排序树T’中，则T与T’是相同的，这种说法是否正确？22.关键字序列为（47，7，29，11，16，92，22，8，3，50，37，89，94，21），哈希函数为：Hash(key)=keymod11，用拉链表处理冲突。23.设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有①front=11，rear=19；②front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？24.数据结构中，度量一个程序的执行时间通常有两种方法：（）。A、事后统计方法B、事前分析估算的方法C、空间复杂度分析法D、渐近式分析方法25.二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范圈从1到10。从供选择的答案中选出正确答案。若A按行存放，元素A[8，5]的起始地址与A按列存放时的元素（）的起始地址一致。A、A[8，5]B、A[3，10]C、A[5，8]D、A[0，9]26.字符串的长度是指（）A、串中不同字符的个数B、串中不同字母的个数C、串中所含字符的个数D、串中不同数字的个数27.排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（）。A、希尔排序B、冒泡排序C、插入排序D、选择排序28.简述二叉树的常用操作及各操作的含义。29.设循环队列中数组的下标范围是1～n，其头尾指针分别为f和r，则其元素个数为（）A、r-fB、r-f+lC、（r-f） mod （n+1）D、（r-f+n） mod n30.为了方便地对图状结构的数据进行存取操作，则其中数据存储结构宜采用（）。A、顺序存储B、链式存储C、索引存储D、散列存储31.用一维数组存储二叉树时，总是以前序遍历存储结点。32.数据结构包括数据的（）结构和（）结构。33.数据结构里，树是一种特殊的一对多的逻辑结构，当一个结点也没有时，它就称为（）。A、满树B、空树C、二叉树D、多叉树34.数据结构中评价算法的两个重要指标是（）和（）35.在所有排序方法中，（）排序方法采用的是二分法的思想。36.从逻辑上可以把数据结构分为（）两大类。A、动态结构、静态结构B、顺序结构、链式结构C、线性结构、非线性结构D、初等结构、构造型结构37.完全二叉树的存储结构通常采用顺序存储结构。38.在动态查找表中，（）既拥有类似折半查找的特性，又采用了链接存储结构。39.假定front和rear分别为一个链队的队首和队尾指针，则该链队中只有一个结点的条件为（）。40.已知模式串t=‘abcaabbabcab’写出用KMP法求得的每个字符对应的next和nextval函数值。41.构造哈希函数的方法有（）、（）、（）42.对图所示的无向图，依次输入各边：（v1，v2）、（v1，v4）、（v2，v3）、（v3，v4）、（v3，v5），请回答下列各问： 写出该无向图的二元组表示。43.在长度为64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为（）A、63B、64C、6D、744.一棵无向连通图的生成树是其极大的连通子图45.单链表的查找很方便，直接可以获得任何一个元素。46.数据的逻辑结构可以形式的用一个二元组B=（K，R）来表示，其中K是（）R是*（）。47.已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，…，nk个度为k的结点，问该树中有多少个叶子结点？48.假定一组记录为(46,79,56,38,40,80)，对其进行快速排序的过程中，含有两个或两个以上元素的排序区间的个数为（）个。49.n个顶点的无向图，采用邻接矩阵存储，回答下列问题： ⑴图中有多少条边？ ⑵任意两个顶点i和j是否有边相连？ ⑶任意一个顶点的度是多少？50.在对n个元素进行冒泡排序的过程中，至少需要（）趟完成。A、1B、nC、n-1D、n/251.具有N（N-1）/2条边的无向图成为（）。52.含n个顶点的连通图中的任意一条简单路径，其长度不可能超过（）。A、1B、n/2C、n-1D、n53.己知输入序列为1234，则输入受限仅由一端输入但输出不受限两端均可输出的双端队列不可以得到（）输出序列。A、4231B、1324C、3214D、4213E、234154.设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（）A、5，3，4，6，1，2B、3，2，5，6，4，1C、3，1，2，5，4，6D、1，5，4，6，2，355.数据结构里，顺序存储结构是数据的（）。A、逻辑结构B、存储结构C、操作D、没有关系56.（）可以看做是从具体问题抽象出来的数学模型。57.二叉树中每个结点的度不能超过2，所以二叉树是一种特殊的树。58.一个数组元素a[i]与（）的表示等价。A、*（a+i）B、a+iC、*a+iD、&a+i59.已知一个堆为（12，15，40，38，26，52，48，64），若需要从堆中依次删除四个元素，请给出每删除一个元素后堆的状态。60.编写算法，实现带头结点单链表的逆置算法。61.在一个具有n个顶点的无向图中，要连通所有顶点则至少需要（）条边。62.循环链表的结点与单链表的结点结构完全相同，只是结点间的连接方式不同。63.树的后根遍历序列等同于与该树对应的二叉树的哪种序列？（）A、 前序序列B、 中序序列C、 后序序列D、 层序序列64.哈夫曼树是其树的带权路径长度（）的二叉树。65.在双向链表中，每个结点含有两个指针域，一个指向（）结点，另一个指向（）结点。66.数据结构研究的三方面内容之间有什么联系和区别？67.在线性表的单链接存储结构中，每个结点包含有两个域，一个叫（）域，另一个叫（）域。68.设有一个长度为s的字符串，其字符顺序存放在一个一维数组的第1至第s个单元中（每个单元存放一个字符）。现要求从此串的第m个字符以后删除长度为t的子串，m＜s，t＜（s-m），并将删除后的结果复制在该数组的第s单元以后的单元中，试设计此删除算法。69.列举几个字符串的其他操作。70.设某散列表的长度为100，散列函数H（k）=k%P，则P通常情况下最好选择（）A、99B、97C、91D、9371.深度为90的满二叉树，第11层有（）个结点。72.设完全无向图中有n个顶点，则该完全无向图中有（）条边。A、n（n-1）/2B、n（n-1）C、n（n+1）/2D、（n-1）/273.某无向图的邻接矩阵A=，可以看出，该图共有（）个顶点。A、3B、6C、9D、以上答案均不正确74.满二叉树是（）。A、所有的分支结点都存在左子树和右子树，并且所有叶子都在同一层上。B、所有的分支结点都存在左子树和右子树，并且所有叶子都在最后两层上。C、所有的分支结点只存在左子树，并且所有叶子都在最后两层上。D、都不对75.直接选择排序算法在最好情况下的时间复杂度为O（n）。第1卷参考答案一.参考题库1.参考答案：D2.参考答案：A3.参考答案：所谓行序优先存储，其基本思想为：从第1行的元素开始按顺序存储，第1行元素存储完成后，再按顺序存储第2行的元素，然后依次存储第3行，……直到最后一行的所有元素存储完毕为止。而列序优先存储即为：依次按顺序存储第1列，第2列，……直到最后一列的所有元素存储完毕为止。4.参考答案：出度5.参考答案：数据元素关系6.参考答案：A7.参考答案：双向栈其实和单向栈原理相同，只是在一个向量空间内，好比是两个头对头的栈放在一起，中间的空间可以充分利用。双向栈的算法设计如下： //双向栈的栈结构类型与以前定义略有不同 8.参考答案：D9.参考答案：B10.参考答案：正确11.参考答案：C12.参考答案：178413.参考答案：A,B,C,D14.参考答案：P->link=top；top=p15.参考答案：采用堆排序最合适，依题意可知只需取得第k个最小元素之前的排序序列时，堆排序的时间复杂度Ο（n+klog2n），若k≤nlog2n，则得到的时间复杂性是Ο（n）。 对于上述序列得到其前4个最小元素，使用堆排序实现时，执行的比较次数如下：初始建堆：比较20次，得到6； 第一次调整：比较5次，得到7； 第二次调整：比较4次，得到9； 第三次调整：比较5次，得到11。16.参考答案：D17.参考答案：B18.参考答案：正确19.参考答案：正确20.参考答案：A21.参考答案：算法的渐近时间复杂度是对算法的时间效率的度量。也就是对一个算法执行所需要的时间进行分析。一个算法执行所需要的具体时间与所使用的计算机系统的软、硬件性能及问题的规模等因素有关。为了比较算法本身的时间性能，应该采用能够反映算法本身的时间性能的度量。实际上，通常算法运行所需要的时间T是问题规模n的函数，可记为T（n）。所谓算法的渐近时间复杂度，是当问题规模充分大时，算法运行时间的增长趋势的度量。因为增长率的上限对算法的比较更具意义，所以经常分析的是算法运行时间的增长率的上限，这就是算法的时间复杂度的大O表示，也常简称为算法的时间复杂度。 为了分析一个算法的时间复杂度，一般情况下需要考察算法中基本语句的执行次数，找出其与问题规模n的函数关系f（n），从而得到算法的渐近时间复杂度。所谓基本语句是执行次数与算法的执行次数成正比的语句，它是算法中的关键操作。算法的基本语句大多包含在循环和递归结构中，对于单循环结构，循环体中的简单语句就是基本语句，其执行次数的大O表示就是该算法段的渐近时间复杂度；对于并列的循环结构，要先分析各个循环结构的渐近时间复杂度，然后利用大O表示法的加法规则求出算法的时间复杂度；对于多层嵌套的循环结构，最内层循环中的简单语句就是算法的基本语句，要自外向内逐层分析各层循环的渐近时间复杂度，再利用大O表示法的乘法规则来求出算法的渐近时间复杂度。对于递归结构，则可以根据递归过程递推出基本语句的执行次数，进而得到它的大O表示。总之，只要分析求出算法中关键操作的执行次数与问题规模的函数关系，也就得到了该次数的大O表示，从而也就求出了算法的渐近时间复杂度。22.参考答案：23.参考答案：824.参考答案：25.参考答案：D26.参考答案：树型27.参考答案：B28.参考答案：头指针是链表的一个标识，它用来指向带头结点的链表中的头结点。头结点是在链表的第一个数据元素之前附加的一个结点，它的作用是使对第一个结点的操作和其它结点一致，表空与非空时处理一致，不需要特殊处理，简化了操作。29.参考答案：D30.参考答案：程序段的功能是利用tmp栈将一个非空栈S1的所有元素按原样复制到一个栈S2当中去。31.参考答案：在插入元素之前，首先要判断栈是否为满，如果栈满，返回“沾满无法插入”等错误提示信息；否则让top指针（指向当前顺序栈的栈顶）向后移动一个元素空间（元素大小），将要插入的元素放入top指针指向的内存单元中。32.参考答案：A33.参考答案：正确34.参考答案：A35.参考答案：9736.参考答案：head->next=haed->prior；head->next=head37.参考答案：C38.参考答案：错误39.参考答案：C40.参考答案：41.参考答案：数据42.参考答案：head->next=head43.参考答案：用元素在存储器中的相对位置来表示数据元素之间的逻辑关系；用指示元素存储地址的指针表示数据元素之间的逻辑关系。44.参考答案：对二叉排序树来讲，其中序遍历序列为一个递增序列。因此，对给定二叉树进行中序遍历，如果始终能够保证前一个值比后一个值小，则说明该二叉树是二叉排序树。 具体算法如下： 45.参考答案：A46.参考答案：D47.参考答案：D48.参考答案：A49.参考答案：错误50.参考答案：树根；双亲（或前驱）；孩子（或后继）51.参考答案：正确52.参考答案：D53.参考答案：A,B54.参考答案：错误55.参考答案：B56.参考答案：头结点57.参考答案：B58.参考答案：D59.参考答案：D60.参考答案：错误61.参考答案：(x,y,z)62.参考答案：正确63.参考答案：使空表和非空表统一，算法处理一致64.参考答案：散列函数：H（K）=k%m其中依题意得m=13 H（32）=32%13=6 H（5）=75%13=10 H（29）=29%13=3 H（63）=63%13=11 H（8）=48%13=9 H（94）=94%13=3（冲突） 设d0=H（K）=H（94）=3 d1=（d0+1）%m=（3+1）%13=4 H（25）=25%13=12 H（46）=46%13=7 H（18）=18%13=5 H（70）=70%13=5（冲突） 设d0=H（K）=H（70）=5 d1=（d0+1）%m=（5+1）%13=6（冲突） d2=（d1+1）%m=（6+1）%13=7（冲突） d3=（d2+1）%m=（7+1）%13=8 ASL=（8*1+1*2+1*4）/10=1.4 65.参考答案：B66.参考答案：B67.参考答案：顺序；链接68.参考答案：469.参考答案：D70.参考答案：B71.参考答案： 72.参考答案：正确73.参考答案：A,B,C74.参考答案：D75.参考答案：栈第2卷参考答案一.参考题库1.参考答案：72.参考答案：循环链表；循环双链表；双链表3.参考答案：B4.参考答案：A5.参考答案：正确6.参考答案：DABEC7.参考答案：8.参考答案：A9.参考答案：C10.参考答案：C11.参考答案：A12.参考答案：深度；广度13.参考答案：正确14.参考答案：D15.参考答案：B16.参考答案：其逻辑结构图如图1-3所示，它是一种图结构。 17.参考答案：A,B,C18.参考答案：A19.参考答案：A20.参考答案：衡量算法的标准有很多，时间复杂度只是其中之一。尽管有些算法时间性能很好，但是其他方面可能就存在着不足。比如散列查找的时间性能很优越，但是需要关注如何合理地构造散列函数问题，而且总存在着冲突等现象，为了解决冲突，还得采用其他方法。 二分查找也是有代价的，因为事先必须对整个查找区间进行排序，而排序也是费时的，所以常应用于频繁查找的场合。对于顺序查找，尽管效率不高，但却比较简单，常用于查找范围较小或偶而进行查找的情况。21.参考答案：正确22.参考答案：23.参考答案：用队列长度计算公式：（N＋r－F)%N ①L=（40＋19－11）%40=8②L=（40＋11－19）%40=3224.参考答案：A,B25.参考答案：B26.参考答案：C27.参考答案：C28.参考答案：创建一棵空二叉树：创建一棵没有任何结点的二叉树。在顺序表示中，根据树的深度为结点分配内存；在二叉链表表示中，将指向根结点的指针赋值为NULL。 删除一棵二叉树：将二叉树各结点所占据的内存释放。 清空二叉树：将二叉树的所有结点删除，使之成为一棵空二叉树。 以指定元素值创建根结点：创建根结点，并以指定值作为根结点的元素值。 将一个结点作为指定结点的左