下载文档原格式
2022年中国矿业大学计算机科学与技术专业《数据库原理》科目期末试卷A（有答案）一、填空题1、安全性控制的一般方法有____________、____________、____________、和____________视图的保护五级安全措施。
2、SQL Server中数据完整性包括______、______和______。
3、以子模式为框架的数据库是______________；以模式为框架的数据库是______________；以物理模式为框架的数据库是______________。
4、如果多个事务依次执行，则称事务是执行______；如果利用分时的方法，同时处理多个事务，则称事务是执行______。
5、设有关系模式R（A，B，C）和S（E，A，F），若R.A是R的主码，S.A是S的外码，则S.A的值或者等于R中某个元组的主码值，或者______取空值，这是规则，它是通过______和______约束来实现的。
6、数据库管理系统的主要功能有______________、______________、数据库的运行管理以及数据库的建立和维护等4个方面。
7、数据仓库主要是供决策分析用的______，所涉及的数据操作主要是______，一般情况下不进行。
8、在VB 6.0中，已经用Adobel连接到数据库，并已绑定到数据库中的某个关系表，现要通过此控件向表中插入数据，需要用到Adobel.Recordset的_____方法和Update方法，使用Adobel.Recordset的_____方法可以使当前行指针在结果集中向前移动一行。
9、在SQL Server 2000中，数据页的大小是8KB。
某数据库表有1000行数据，每行需要5000字节空间，则此数据库表需要占用的数据页数为_____页。
10、数据库恢复是将数据库从______状态恢复到______的功能。
二、判断题11、在关系数据库中，属性的排列顺序是可以颠倒的。
数据构造期末考试题及答案一、选择题1．在数据构造中，从逻辑上可以把数据构造分为C。
A．动态构造和静态构造B．紧凑构造和非紧凑构造C．线性构造和非线性构造D．内部构造和外部构造2．数据构造在计算机内存中旳表达是指A。
A．数据旳存储构造B．数据构造C．数据旳逻辑构造D．数据元素之间旳关系3．在数据构造中，与所使用旳计算机无关旳是数据旳A构造。
A．逻辑B．存储C．逻辑和存储D．物理4．在存储数据时，一般不仅要存储各数据元素旳值，并且还要存储C。
A．数据旳解决措施B．数据元素旳类型C．数据元素之间旳关系D．数据旳存储措施5．在决定选用何种存储构造时，一般不考虑A。
A．各结点旳值如何B．结点个数旳多少C．对数据有哪些运算D．所用旳编程语言实现这种构造与否以便。
6．如下说法对旳旳是D。
A．数据项是数据旳基本单位B．数据元素是数据旳最小单位C．数据构造是带构造旳数据项旳集合D．某些表面上很不相似旳数据可以有相似旳逻辑构造7．算法分析旳目旳是C，算法分析旳两个重要方面是A。
（1）A．找出数据构造旳合理性B．研究算法中旳输入和输出旳关系C．分析算法旳效率以求改善C．分析算法旳易读性和文档性（2）A．空间复杂度和时间复杂度B．对旳性和简要性C．可读性和文档性D．数据复杂性和程序复杂性8．下面程序段旳时间复杂度是O（n2）。
s ＝0；for（I ＝0；i＜n；i＋＋）for（j＝0；j＜n；j＋＋）s ＋＝B[i][j]；sum ＝s ；9．下面程序段旳时间复杂度是O（n*m）。
for（i ＝0；i＜n；i＋＋）for（j＝0；j＜m；j＋＋）A[i][j] ＝0；10．下面程序段旳时间复杂度是O（log3n）。
i ＝0；while（i＜＝n）i ＝i * 3；11．在如下旳论述中，对旳旳是B。
A．线性表旳顺序存储构造优于链表存储构造B．二维数组是其数据元素为线性表旳线性表C．栈旳操作方式是先进先出D．队列旳操作方式是先进后出12．一般规定同一逻辑构造中旳所有数据元素具有相似旳特性，这意味着 B 。
2022年三峡大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。
A.快速排序B.堆排序C.归并排序D.直接插入排序2、n个结点的完全有向图含有边的数目（）。
A.n*nB.n(n+1)C.n/2D.n*(n-1)3、若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（）。
A.单链表B.双向链表C.单循环链表D.顺序表4、下面关于串的叙述中，不正确的是（）。
A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储5、已知串S='aaab'，其next数组值为（）。
A.0123B.1123C.1231D.12116、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。
A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝27、下列选项中，不能构成折半查找中关键字比较序列的是（）。
A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，4508、在下述结论中，正确的有（）。
①只有一个结点的二叉树的度为0。
②二叉树的度为2。
③二叉树的左右子树可任意交换。
④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。
A.①②③B.⑦③④C.②④D.①④9、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。
A.其中任意一个结点均无左孩子B.其中任意一个结点均无右孩子C.其中只有一个叶结点D.其中度为2的结点最多为一个10、分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（）。
2022年中国矿业大学数据科学与大数据技术专业《计算机网络》科目期末试卷A（有答案）一、选择题1、比特的传播时延与链路带宽的关系是（）。
A.没有关系B.反比关系C.正比关系D.无法确定2、计算机网络最基本的功能是（）。
I.流量控制Ⅱ.路由选择 III.分布式处理 IV.传输控制A.I、Ⅱ、IVB. I、III、ⅣC.I、IVD. Ⅲ、IV3、有一个TCP连接，当其拥塞窗口为32个分组大小时超时。
假设网络的RTT是固定的5s，不考虑比特开销，即分组不丢失，则系统在超时后处于慢启动阶段的时间有（）。
A.10sB.20sC.30sD.40s4、oS17层模型中，提供端到端的透明数据传输服务、差错控制和流量控制的层是（）。
A.物理层B.网络层C.传输层D.会话层5、为了纠正2比特的错误，编码的海明距应该为（）。
A.2B.3C.4D.56、HDLC协议对0111110001111110组帧后对应的比特串为（）A.01111100 0011111010B.01111100 01111101 01111110C.01111100 0111110103D.0111110001111110011111017、波特率等于（）A.每秒传输的比特B.每秒可能发生的信号变化次数C.每秒传输的周期数D.每秒传输的字节数8、对一个无噪声的4kHz信道进行采样，可达到的最大数据传输率是（）A.4kbit/sB.8kbit/sC.1kbit/sD.无限大9、当集线器的某个端口收到数据后，其动作为（）A.从所有端口广播出去B.从除了输入端口外的所有端口广播出去C.根据目的地址从合适的端口转发出去D.随机选择一个端口转发出去10、从协议分析的角度，www服务的第一步操作是www浏览器完成对wwW服务器的（）。
A.地址解析B.域名解析C.传输连接建立D.会话连接建立11、图所示的曼彻斯特编码表示的比特串为（）A.011001B.100110C.111110D.01111012、把IP网络划分成子网，这样做的好处是（）。
2022年复旦大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、用有向无环图描述表达式(A+B)*((A+B)／/A)，至少需要顶点的数目为（）。
A.5B.6C.8D.92、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。
A.NB.2N-1C.2ND.N-13、线性表的顺序存储结构是一种（）。
A.随机存取的存储结构B.顺序存取的存储结构C.索引存取的存储结构D.Hash存取的存储结构4、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）。
A.仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都可能要修改D.队头、队尾指针都要修改5、在下列表述中，正确的是（）A.含有一个或多个空格字符的串称为空格串B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树C.选择排序算法是不稳定的D.平衡二叉树的左右子树的结点数之差的绝对值不超过l6、下列关于无向连通图特性的叙述中，正确的是（）。
Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1 A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ7、已知关键字序列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，198、在下述结论中，正确的有（）。
①只有一个结点的二叉树的度为0。
②二叉树的度为2。
③二叉树的左右子树可任意交换。
④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。
A.①②③B.⑦③④C.②④D.①④9、下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（）。
2022年中原工学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、将线性表的数据元素进行扩充，允许带结构的线性表是（）。
A.串B.树C.广义表D.栈2、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）。
A.60B.66C.18000D.333、连续存储设计时，存储单元的地址（）。
A.一定连续B.一定不连续C.不一定连续D.部分连续，部分不连续4、已知串S='aaab'，其next数组值为（）。
A.0123B.1123C.1231D.12115、下列关于AOE网的叙述中，不正确的是（）。
A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，那么整个工程将会提前完成C.所有的关键活动提前完成，那么整个工程将会提前完成D.某些关键活动若提前完成，那么整个工程将会提前完成6、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。
A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝27、下列叙述中，不符合m阶B树定义要求的是（）。
A．根结点最多有m棵子树 B．所有叶结点都在同一层上C．各结点内关键字均升序或降序排列 D．叶结点之间通过指针链接8、下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（）。
A.二叉排序树B.哈夫曼树C.AVL树D.堆9、每个结点的度或者为0或者为2的二叉树称为正则二叉树。
n个结点的正则二叉树中有（）个叶子。
A.log2nB.（n－1）/2C.log2n+1D.（n＋1）/210、一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。
数据结构复习题（课程代码 252259）一、填空题（本大题共40小题）1.队列中是按照______先进先出______的原则进行数据元素的增删。
2.___栈__又称为LIFO表。
3.在顺序存储的完全二叉树中，若编号为i的结点有左孩子结点，则其右孩子结点的编号为___2i+1___。
4.存储地址与关键字之间存在某种映射关系的存储结构为_______散列存储结构_______。
5.在串S=“structure”中，以r为首字符的子串有_9_个。
6.设有整型二维数组M[4][3]，每个元素（整数）占2个存储单元，元素按行的顺序存储，数组的起始地址为200，元素M[1][1]的地址是___208____。
7.在一个具有n个顶点的无向完全图中，包含有___ n(n-1)/2_____条边，在一个具有n个顶点的有向完全图中，包含有__ n(n-1)______条边。
8.假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为_____（12，40）（）（74）（23,55，63）____。
9.向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度____增加1______。
10.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为__ O(log2n)______，整个堆排序过程的时间复杂度为__ O(nlog2n)______。
11.在快速排序、堆排序、归并排序中，____归并_____排序是稳定的。
12.一棵深度为5的满二叉树中的结点数为_______31_______个。
13.在含n个顶点和e条边的无向图的邻接矩阵中,非零元素的个数为__2e __。
14.从一棵二叉排序树中查找一个元素时，若元素的值大于根结点的值，则继续向____右子树____查找。
15._____拓朴排序______可以判断出一个有向图中是否有环。
2022年中国矿业大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。
A.快速排序B.堆排序C.归并排序D.直接插入排序2、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（）排序法。
A.插入B.选择C.希尔D.二路归并3、计算机算法指的是解决问题的步骤序列，它必须具备（）三个特性。
A.可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性C.确定性、有穷性、稳定性D.易读性、稳定性、安全性4、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行（）。
A.h->next=sB.s->next=hC.s->next=h;h->next=sD.s->next=h-next;h->next=s5、在下列表述中，正确的是（）A.含有一个或多个空格字符的串称为空格串B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树C.选择排序算法是不稳定的D.平衡二叉树的左右子树的结点数之差的绝对值不超过l6、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。
下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。
Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序A．仅Ⅰ、Ⅲ、Ⅳ B．仅Ⅰ、Ⅱ、Ⅲ C．仅Ⅱ、Ⅲ、Ⅳ D．仅Ⅲ、Ⅳ、Ⅴ7、若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（）。
8、有关二叉树下列说法正确的是（）。
A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为29、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。
单选题（每题 2 分，共20分）1. 对一个算法的评价，不包括如下（B ）方面的内容。
A．健壮性和可读性B．并行性C．正确性D．时空复杂度2. 在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( A )。
A. p->next=HL->next; HL->next=p;B. p->next=HL; HL=p;C. p->next=HL; p=HL;D. HL=p; p->next=HL;3. 对线性表，在下列哪种情况下应当采用链表表示？( B )A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变4. 一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( C )A. 2 3 1B. 3 2 1C. 3 1 2D. 1 2 36. 若需要利用形参直接访问实参时，应将形参变量说明为（D ）参数。
A．值B．函数C．指针D．引用8. 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（A ）。
A．行号B．列号C．元素值D．非零元素个数10. 从二叉搜索树中查找一个元素时，其时间复杂度大致为(C )。
A. O(n)B. O(1)C. O(log2n)D. O(n2)二、运算题（每题6 分，共24分）1. 数据结构是指数据及其相互之间的_联系。
当结点之间存在M对N（M：N）的联系时，称这种结构为__图__。
2. 队列的插入操作是在队列的___尾_进行，删除操作是在队列的_首_进行。
3. 当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件是___top==0___(要超出才为满)_______________。
4. 对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为___ O（1）__，在表尾插入元素的时间复杂度为___ O（n）___。
2022年中央财经大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、已知广义表LS=（（a，b，c），（d，e，f）），用head和tail数取出LS中原子e 的运算是（）。
A.head（tail（LS））B.tail（head（LS））C.head（tail（head（tail（LS））））D.head（tail（tail（head（LS））））2、将线性表的数据元素进行扩充，允许带结构的线性表是（）。
A.串B.树C.广义表D.栈3、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。
A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表4、动态存储管理系统中，通常可有（）种不同的分配策略。
A.1B.2C.3D.45、下列关于AOE网的叙述中，不正确的是（）。
A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，那么整个工程将会提前完成C.所有的关键活动提前完成，那么整个工程将会提前完成D.某些关键活动若提前完成，那么整个工程将会提前完成6、下列选项中，不能构成折半查找中关键字比较序列的是（）。
A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，4507、若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（）。
8、在下述结论中，正确的有（）。
①只有一个结点的二叉树的度为0。
②二叉树的度为2。
③二叉树的左右子树可任意交换。
④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。
A.①②③B.⑦③④C.②④D.①④9、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。
A.其中任意一个结点均无左孩子B.其中任意一个结点均无右孩子C.其中只有一个叶结点D.其中度为2的结点最多为一个10、对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（）。
2022年中国矿业大学(北京)计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。
A.NB.2N-1C.2ND.N-12、已知广义表LS=（（a，b，c），（d，e，f）），用head和tail数取出LS中原子e的运算是（）。
A.head（tail（LS））B.tail（head（LS））C.head（tail（head（tail（LS））））D.head（tail（tail（head（LS））））3、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。
A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表4、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。
A.543612B.453126C.346521D.2341565、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行（）。
A.h->next=sB.s->next=hC.s->next=h;h->next=sD.s->next=h-next;h->next=s6、已知关键字序列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，197、下列叙述中，不符合m阶B树定义要求的是（）。
A．根结点最多有m棵子树 B．所有叶结点都在同一层上C．各结点内关键字均升序或降序排列 D．叶结点之间通过指针链接8、每个结点的度或者为0或者为2的二叉树称为正则二叉树。
n个结点的正则二叉树中有（）个叶子。
A.log2nB.（n－1）/2C.log2n+1D.（n＋1）/29、有关二叉树下列说法正确的是（）。
A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为210、就平均性能而言，目前最好的内排序方法是（）排序法。
A.起泡B.希尔插入C.交换D.快速二、填空题11、若用n表示图中顶点数目，则有______条边的无向图成为完全图。
12、下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。
如123存放成321。
请填空：13、外排序的基本操作过程是______和______。
14、VSAM（虚拟存储存取方法）文件的优点是：动态地______，不需要文件进行______，并能较快地______进行查找。
15、对于一个具有n个结点的单链表，在已知的结点半p后插入一个新结点的时间复杂度为______，在给定值为x的结点后插入一个新结点的时间复杂度为______。
16、下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。
17、一棵有n个结点的满二叉树有______个度为1的结点、有______个分支（非终端）结点和______个叶子，该满二叉树的深度为______。
18、在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是______。
三、判断题19、对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。
（）20、倒排文件的目的是为了多关键字查找。
（）21、数组不适合作为任何二叉树的存储结构。
（）22、在链队列中，即使不设置尾指针也能进行入队操作。
（）23、深度为k的二叉树中结点总数小于等于2k-1。
（）24、一般来说，若深度为k的n个结点的二叉树只有最小路径长度，那么从根结点到第k-1层具有的最多结点数为2k-1-1，余下的n-2k-1+1个结点在第k层的任一位置上。
（）25、数据元素是数据的最小单位。
（）26、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
（）27、平衡二叉树中，若某个结点的左、右孩子的平衡因子为零，则该结点的平衡因子一定是零。
（）28、对两棵具有相同关键字集合的而形状不同的二叉排序树，按中序遍历它们得到的序列的顺序却是一致的。
（）四、简答题29、设目标为t=‘abcaabbabcabaacbacba’，模式为P=‘abcabaa’（1）计算模式p的nextval函数值。
（2）不写出算法，只画出利用KMP算法进行模式匹配时每一趟的匹配过程。
30、给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程：（1）归并排序，每归并一次书写一个次序。
（2）快速排序，每划分一次书写一个次序。
（3）堆排序，先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。
31、二叉树的带权路径长度（WPL）是二叉树中所有叶结点的带权路径长度之和，给定一棵二叉树T，采用二叉链表存储，节点结构为：其中叶节点的weight域保存该结点的非负权值。
设root为指向T的根节点的指针，设计求T的WPL的算法。
要求：（1）给出算法的基本设计思想。
（2）使用C或C++语言，给出二叉树结点的数据类型定义。
（3）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
五、算法设计题32、设A[1..100]是一个记录构成的数组，B[1..100]是一个整数数组，其值介于l～100之间，现要求按B[1..100]的内容调整A中记录的次序，比如当B[1]=11时，则要求将A[1]的内容调整到A[11]中去。
规定可使用的附加空间为O（1）。
33、给出以十字链表作存储结构，建立图的算法，输入(i，j，v)，其中i，j为顶点号，v 为权值。
34、假定用两个一维数组L[N]和R[N]作为有N个结点1，2，…，N的二叉树的存储结构。
L[i]和R[i]分别指示结点i的左儿子和右儿子， L[i]=0（R[i]=0）表示i的左（右）儿子为空。
试写一个算法，由L和R建立一个一维数组T[n]，使T[i]存放结点i的父亲；然后再写一个判别结点u 是否为结点V的后代的算法。
35、写出算法，求出中序线索二叉树中给定值为x的结点之后继结点，返回该后继结点的指针。
线索树中结点结构为：（ltag，lc，data，rc，rtag）。
其中，data存放结点的值；lc、rc为指向左、右孩子或该结点前驱、后继的指针，ltag、rtag为标志域，若值为0，则lc、rc为指向左、右孩子的指针；若值为1，则lc、rc为指向其前驱、后继结点的指针。
参考答案一、选择题1、【答案】A2、【答案】C3、【答案】A4、【答案】C5、【答案】D6、【答案】A7、【答案】D8、【答案】D9、【答案】B10、【答案】D二、填空题11、【答案】n(n-1)/212、【答案】a+1；n%10【解析】通过递归算法，首先找到最高位的值，将其放到str对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。
13、【答案】生成有序归并段（顺串）；归并14、【答案】分配和释放存储空间；重组；对插入的记录@15、【答案】O（1）；O（n）16、【答案】a[j]=a[k]；low=stack[top][0]；stack[top][0]=k+1【解析】快速排序(quick sort)的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
17、【答案】【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。
18、【答案】++a*b3*4-cd；18【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。
三、判断题19、【答案】×20、【答案】√21、【答案】×22、【答案】√23、【答案】√24、【答案】√25、【答案】×26、【答案】×27、【答案】×28、【答案】√四、简答题29、答：（1）p的nextval函数值为0110132（p的next函数值为0111232）。
（2）利用KMP（改进的nextval）算法，每趟匹配过程如下：30、答：（1）2一路归并第一趟：18，29，25，47，12，58，10，51。
第二趟：18，25，29，47，10，12，51，58。
第三趟：10，12，18，25，29，47，51，58。
（2）快速排序第一趟：10，18，25，12，29，58，51，47。
第二趟：10，18，25，12，29，47，51，88。
第三趟：10，12，18，25，29，47，51，88。
（3）堆排序建大堆：58，47，51，29，18，12，25，10。
①51，47，25，29，18，12，10，58。
②47，29，25，10，18，12，51，58。
③29，18，25，10，12，47，51，58。
④25，18，12，10，29，47，51，58。
⑤18，10，12，25，29，47，51，58。
⑥12，10，18，25，29，47，51，58。
⑦10，12，18，25，29，47，51，58。
31、答：（1）算法的基本思路是利用递归的思想来求解二叉树的带权路径长度，如果当前节点不是叶子节点，那么当前节点为根的树的带权路径长度便等于它的子树的带权路径长度之和，对于此函数要传入一个当前节点的树高的形参，那么递归调用孩子节点时只需要将这个形参加一即可。
（2）五、算法设计题32、答：算法如下：33、答：算法如下：34、答：算法如下：35、答：算法如下：。
