《数据结构期末考试题总.pdf》由会员分享，可在线阅读，更多相关《数据结构期末考试题总.pdf（40页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、一、判断题1、栈是限定仅在表尾进行插入和删除操作的线性表。（J）2、引入循环队列的目的是为了克服假溢出时大量移动数据元素。（J ）3、区分循环队列的满与空，有牺牲一个存储单元和设标记两种方法。（J）4、若一个栈的输入序列为1,2,3,则3,1,2是不可能的栈输出序列。35、表达式求值是队列应用的 个典型例子。（X）6、任何一个递归过程都可以转换成非递归过程。（J ）7,循环队列也存在空间溢出问题。（J）8、栈和队列都是线性表，只是在插入和删除时受到了一些限制。（V）9、K MP算法的特点是在模式匹配时指示主串的指针不会变小。3）1 0、串是一种数据对象和操作都特殊的线性表。（V）1 1、对称矩
2、阵压缩存储后不会失去随机存取功能。（J）1 2、数组可看成线性结构的一种推广，可以对它进行插入，删除等操作。（X）1 3、一个稀疏矩阵Am Xn采用三元组形式表示，若把三元组中有关行下标与列卜标的值互换，并把m 和n的值互换，则完成了 Am Xn的转置运算。（X）1 4、二维以上的数组其实是一种特殊的广义表。1 5、广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。（X）1 6、若一个广义表的表头为空表，则此广义表亦为空表。（X）1 7、广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。（X）1 8、所谓取广义表的表尾就是返回广义表中最后一个元素。（X）1 9、广义表
3、的同级元素具有线性关系。（V）2 0、一个广义表可以为其它广义表所共享。（-J）2 1、压缩存储的三角矩阵和对称矩阵的存储空间相同。（）解答：压缩存储的三角矩阵比压缩存储的对称矩阵多一个存储空间，用来存储常量c。答案：X2 2、广义表中的数据元素类型可以不相同。（）解答：广义表的不同元素可以有不同的结构，即数据元素类型可以不相同。答案：J2 3、广义表的元素不可以是广义表。（）解答：广义表的元素可以是子表，子表的元素还可以是子表，即广义表是一个多层次的结构。答案：X2 4、两个稀疏矩阵的和仍为稀疏矩阵。（）解答：两个稀疏矩阵的和不一定是稀疏矩阵。例如，当两个稀疏矩阵和的非0元个数等于这两个稀疏
4、矩阵非 0 元个数之和时，这两个矩阵的和不一定是稀疏矩阵。答案：X2 5、数组用顺序存储方式存储时;存取每个元素的时间相同。（）解答：数组用顺序存储方式存储时，只要知道起始结点的存放地址（即基地址）、维数和每维的上、下界，以及每个数组元素所占用的字节数，就可以将数组元素的存放地址表示为其下标的线性函数。因此，数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。答案：V2 6、队列这种结构是不允许在中间插入和删除数据的。（）解答：队列也是一种特殊的线性表，它只允许在端进行插入操作，在另一端进行删除操作，不允许在中间插入和删除数据。答案：J2 7、循环队列只能用顺序表实现。
5、（）解答：使用循环队列的目的是解决顺序队列的假溢出现象，所以循环队列只能用顺序表实现。答案：，2 8、顺序栈的“栈满”与“上溢”是没区别的，“栈空”与“下溢”是有区别的。（）解答：栈满时若有元素入栈，将产生上溢。栈空时若进行出栈操作，将产生下溢。由此可知，“栈满”与“上溢”有区别的，“栈空”与“下溢”也有区别。答案：X2 9、顺序队列的“假溢出”现象是可以解决的。（）解答：顺序队列的“假溢出”现象可以利用循环队列或通过移动元素的方式解决。答案：V3 0、空串与空格串是一样的。（）解答：空串中没有字符，其长度为0；空格串中含有空格字符，其长度为空格的个数。答案：X3 1.单链表中指针p 所指向结
6、点存在后继结点的条件是p!=N U L L.X3 2、双循环链表从任何结点出发可以访问该结点的直接前驱和直接后继。，3 3、队列是特殊的线性表，在队列的两端可以进行同样的操作。X3 4、双向循环链表从任意结点出发可以访问链表中的任意结点。43 5、头指针一定要指向头结点。（）解答：若链表有头结点，则头指针指向头结点；若链表没有头结点，则头指针指向第一个结点（链表不空），或指向空（链表为空）。答案：X3 6、链表中结点数据域占的存储空间越多，存储密度越大。J3 7、栈是线性表，线性表的所有操作均适用于栈。x3 8、一个三维数组可以看作为是数组元素为二维数组的线性表。J3 9、广义表中的数据元素类
7、型可以不相同。M4 0、串是一种数据对象和操作都特殊的线性表。V4 1、两个稀疏矩阵的和仍为稀疏矩阵。x4 2、串中任意个字符组成的子序列称为该串的子串。x4 3、压缩存储的三角矩阵和对称矩阵的存储空间相同。X4 4、如果两个串含有相同的字符，则这两个串相等。x4 5、数组不适合作为任何二叉树的存储结构。x4 6、在前序遍历二叉树的序列中，任何结点的子树的所有结点都直接跟在该结点之后、Y4 7、若一个树叶是某子树的中序遍历序列中的最后一个结点，则它必是该子树的前序遍历序列中的最后一个结点。V4 8、已知一棵二叉树的前序遍历和后序遍历序列并不能唯一地确定这棵二叉树。M4 9、二叉树用链式存储时，
8、空链域数多于非空链域数。M5 0、K MP算法的特点是在模式匹配时指示主串的指针不会回溯。5 1、后序遍历一棵二叉树等于中序遍历其对应的树。x5 2、满二叉树是完全二叉树。M5 3、单循环链表从任何结点出发可以访问链表中的任何结点（）。解答：将单链表中最后一个结点的指针域由空改为指向头结点，这样的单链表称为单向循环链表。即单向循环链表是，个指向后继有向环，从任意结点出发可以访问链表中的任意结点。答案：V5 4、用顺序表存储线性表时，不需要另外开辟空间保存数据元素之间的相互关系。V55双循环链表从任意结点出发可以访问该结点的直接前驱和直接后继()。解答：将双链表的最后一个结点的后继指针域的值由空
9、改为指向头结点，头结点中的前驱指针域的值由空改为指向尾结点，这样的双向链表称为双向循环链表。即双向循环链表是两个有向环，个是指向后继有向环，另一个是指向前驱的有向环。从任意结点出发都可以访问该结点的直接前驱和直接后继。答案：456、稀疏矩阵压缩存储后，必会失去随机存取功能。457、链表中结点数据域占的存储空间越多，存储密度越大()。解答：存储密度=(结点数据本身所占的存储量)/(结点结构所占的存储总量)由此可知，链表中结点数据域占的存储空间越多，存储密度越大。答案：V58、顺序队列和循环队列的队满和队空的判断条件是一样的。x59、带头结点和不带头结点的单链表在查找、删除、求长度等操作上无区别(
10、)。解答：头结点是为了操作的统一、方便而设立的，放在第一元素结点之前，其数据域一般无意义(当然有些情况卜.也可存放链表的长度、用做监视哨等等)，有头结点后，对在第一元素结点前插入结点和删除第一结点，其操作与对其它结点的操作统一了。而且无论链表是否为空，头指针均不为空。答案：X60、数据的存储结构是数据的逻辑结构的存储映像，不仅要存储数据元素的值，还要存储元素之间的相互关系。461、单链表中指针p 所指向结点存在后继结点的条件是p!=NULL解答：单链表中指针p 所指向结点存在后继结点的条件是p-next!=NULLo答案：X62、线性表中每个结点都有前驱和后继()。解答：线性表中，第一个结点没
11、有前驱，最后一个节点没有后继。答案：X63、广义表的元素不可以是广义表。X64、头结点就是链表中的第I 个结点。()解答：头结点是为了操作的统一、方便而设立的，放在第一元素结点之前，其数据域一般无意义(当然有些情况卜.也可存放链表的长度、用做监视哨等等)，有头结点后，对在第一元素结点前插入结点和删除第一结点，其操作与对其它结点的操作统一了。首元结点也就是第一元素结点，它是头结点后边的第一个结点。答案：X65、线性表中每个结点都有前驱和后继。x66、顺序表可能对存储其中的数据进行排序操作，链表也能进行排序操作。()解答：可以插入和删除操作对链表进行排序。答案：J67、消除递归不一定需要使用栈。X
12、二、单选题1、k=l;fbr(i=0;i n;i+)fbr(j=0;jn;j+)上述程序段的时间复杂度为()。A)O(n2)B)O(n)C)O(2n)D)O(l)2、下面哪一个不是线性表的特性()除最后一个元素外，每个元素都有后继。除第一个元素外，每个元素都有前驱。线性表的长度为n.n邦。线性表是有限序列。3、与线性表的顺序存储不相符的特性是（）。A）插入和掰除操作加活B）需要连续存储空间C）便于随机访问D）存储密度大4、下面哪一个不是顺序表的特点（）。A）逻辑上相邻的元素，存储在计算机中相邻的存储空间B）在顺序表中查找一个元素与表中元素的分布没有关系C）用动态一维数组存储顺序表最合适D）插入
13、一个元素，平均要移动表长一半的数据元素5、与线性表的链接存储不相符合的特性是（）。A）便于插入、删除运算 B）存储空间动态分配C）“此主也的存储空间 D）只能顺序查找6、若线性表采用链式存储，则表中各元素的存储地址A）必须是连续的 B）部分地址必须是连续的C）一定不是连续的D）可以连城也可以不连续7、链表不具有的特点是（）可以随机访问任何一个元素插入和删除元素不需要移动元素不必事先估计存储空间所需存储空间与链表长度成正比8、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用以下哪种存储方式最节省操作时间（）。A）单链表B）仅有头指针的单循环链表C）双链表D）仅 彳j
14、头 指 针 的 双 /next=p-next;p-next=s;p-next=s-next;s-next=p;（3）q-next=s;s-next=p;p-next=s;s-next=q11、链表不具有的特点是（）A.插入、删除操作不需要移动元素 B.可随机访问任一元索C.不必事先估计存储空间 D.所需空间与线性长度成正比12、对于一个线性表，若要求既能够进行较快地插入和删除，又能够反映出数据元素之间的关系，则应该（A.以顺序方式存储 B.以链接方式存储C.以散列方式存储 D.以索引方式存储13、在一个单链表中，已知q所指向的结点是p所指向结点的前驱结点，若在q和p之间插入s所指向的结点，则执
15、行（）。s-next=p-next;p-next=s;p-next=s-next;s-next=p;q-next=s;s-next=p;p-next=s;s-next=q14、在线性表的卜列存储结构中，读取元素花费时间最少的是（）.单链表 双链表 循环链表 顺序表解答：顺序表是随机存取，时间复杂度为0（1）,链表是顺序存取，时间复杂度为0（n）。答案：15、在单链表上插入一个数据结点的平均时间复杂性为()o 0 0(n)0(logm)0(n2)解答：在单链表上插入个数据结点，时间耗费主要是在杳找插入位置上。在长度为n的单链表的第/个结点后插入一个数据元素时，平均查找次数为：1 .1 +1)/?
16、+1 ，=x-=-2 2时间复杂度为0(n)。答案：16、在顺序表上删除一个数据结点的平均时间复杂性为().0 (n)。(logs)0(n2)解答：在顺序表上删除一个数据结点，时间耗费主要是在数据移动操作匕 在长度为n的顺序表中删除一个数据元素时所需移动的数据元素的平均次数为：金 占 n 2 2平均时间复杂度为0(n)。答案：17、非空双循环链表中，在q所指向的结点前插入一个由p所指向结点的过程依次为()。A)p-next=q;p-prior=q-prior;q-prior=p;q-next=p;B)p-next=q;p-prior=q-prior;q-prior=p;q-prior-next
17、=p;C)p-ncxt=q;p-prior=q-prior;q-prior=p;p-prior-ncxt=p;D)p-next=q;p-prior=q-prior;q-prior=p;p-next-prior=p;18、若进栈序列为1,2,3,4,则不可能得到的出栈序列是A)3,2,l,4 B)3,2,4,l C)4,2,3.1 D)2,3,4,l19、在一个具有n个单元的顺序栈中，假定以地址低端作为栈底，以top作为栈顶指针，则当作退栈处理时，top变化为()top 不变top+=n top top+20、设输入序列为1,2,3,4,借助一个栈可以得到的输出序列是()。1,3,4,2 3,1
18、,4,24,3,1,2 4,1,2,321、若进队序列为1,2,3,则出队序列是()。A)3,2,l B)l,2,3 C)1,3,2 D)3,2,l22、栈和队列都是()。A)顺序存储的线性结构B)限制存取小的线忤结构C)链接存储的线性结构D)限制存取点的非线性结构23、栈和队列都是()顺序存储的线性表链式存储的线性表限制插入、删除位置的线性表限制插入、删除操作位置的非线性结构24、若循环队列的队头指针为fro n t,队尾指针为re a r,则队长的计算公式为()。(rcar+M-front)%MA)rear-front B)front-rear C)rear-front+l D)都不 i:
19、确25、在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队列为空的条件是()。A)front=rear+l B)front+1=rear C)front:-rear D)front=026、在一个链队列中，假定front和rear分别为队首指针和队尾指针，则进行插入s所指向结点的操作是()front-next=s;front=s;front=front-next;rear-next=s;rear=s;front=rear-next;27、串 是()一些符号构成的序列一些字母构成的序列一个以上的字符构成的序列任意有限个字符构成的序列28、若将n阶对称
20、矩阵A的 卜三角部分以行序为主序压缩存储到一维数组B中，A的卜标卜.界为0,B的下标下界为1。那么，A中的任一下三角元素aij在矩阵B中的位置为A)i(i+l)/2+j A)i(i+l)/2+j-l C)i(i H)/2+j 1 D)j(j+l)/2+i29、数组A1010的下标下界为1,每个元素占3个字节，存储在起始地址为100的连续内存单元，则元素 A54的地址为().=100+(4*10+3)*3=229 215 270 262 22930、将8阶对称矩阵A的卜三角部分逐行地存储到起始地址为1()0的内存单元中，已知每个元素占4个字节，下标下界都为 0,则 A74的 地 址 为i=j,i
21、*(i+l)/2+j=32 地址=100+32*4=228A)35B)36C)340D)22831、将一个100阶的对称矩阵A按行优先压缩存入一维数组B中,下标的下界都为0,则A中的元素A6564在数组B中的位置为()。A)2194B)2195C)2209D)219732、对稀疏矩阵进行压缩存储的目的是A)便于进行矩阵运算B)便了输入和输出C)省作储)旧D)降低运算的时间复杂度33、下面说法不正确的是()。A)广义点的衣头怠工一个广义之B)广义表的表尾总是一个广义表C)广义表难以用顺序存储结构D)广义表可以是个多层次的结构34、对广义表 A=(x,(a,b),c,d)做运算 head(head
22、(tail(A)后的结果为().A)xB)(a.b)C)aD)c35、广义表(),()的深度为()。A)0 B)1 C)2 D)336、L!知广义表L=(x,y,z),a,(u,t,w),则从L中取出原子项t的操作是()。i hcad(tail(hcad(tail(tail(L)head(head(tail(tail(tail(L)head(tail(tail(tail(taiI(L)head(lail(tail(head(tail(L)37、在树的双亲表示法中对树按层次编号，用数组进行存储，则下面说法不正确的是()。A)兄结点的下标值小于弟结点的下标值B)所有结点的双亲均可以找到。任意结点的
23、孩子信息可以找到D)下标值为i和i+l的结点的关系足孩广和双亲38、有100个结点的完全二叉树由根开始从上到下从左到右对结点进行编号，根结点的编号为1,编号为4 3的 结 点 的 左 孩 子 的 编 号 为 性质5A)50B)48C)98D)8639、在深度为6的完全二叉树中()。最少2 1 1+1,最多211A)最少有31个结点，最多有64个结点B)最少有32结点，最多有6 4个结点C)最少有3 1个结点，最多有63结点D)最少/32 m，最多仃6 3”,也40、假定在一棵二叉树中，度为2的结点数为1 5,度为1的结点数为3 2,则叶子结点个数为()。n0=n2+l性质3A)15B)16C)
24、17D)1841、已知完全二叉树有8 0个结点，则整个二叉树有()个度为1的结点。性质6A)0 B)l C)2 D)不确定42、n个结点的二叉树，若用二叉链表作为存储结构，则非空闲的左、右孩子链域为A)nB)2n C)n-1 D)n+143、假定在一棵二叉树中，度为2的结点数为15个，度为1的结点数为32个，则叶子结点个数为()。A)18 B)17C)16 D)1544、对一棵有n个结点的树，则该树中的度之和为()n n-ln+1 不确定45、在二叉树的先序遍历中，任意一个结点均处在其子孙前面()。根左右A)小:确B)不正确C)有时正确D)不定46、若二叉树的先序遍历序列和后序遍历序列正好相同
25、，则一定是一棵()二叉树不多于一个结点的二叉树结点个数可能大于1且各结点均无左孩子结点个数可能大于1且各结点均无右孩子其中任意个结点的度不为2的47、若一个栈的输出序列的第一个元素是i,则第j个输出元素是()。A.i-j+1 B.i-j C.j-i+1 D.不确定的解析：对输入序列为1,2,3,n,若第一个输出的元素是n,即i=n,则第j个输出的元素是n-j+1,否则不能确定其他元素的输出顺序。例如：输入序列为1 2 3,若第一输出元素是1,则可能的输出序列有123和132。答案：D48、若栈采用顺序存储方式存储，现 两 栈 共 享 空 间topi代表第i个栈(i=l,2)栈顶，栈1的底在v
26、0,栈2的 底 在 则 栈 满 的 条 件 是().A.|top2-topl|=0 B.topl+l=top2C.topl+top2=m D.topl=top2解析：栈1和栈2共享内存中一片连续空间，两栈顶topl和top2向共享空间的中心延伸，仅当两栈顶指针值之差的绝对值等于1时，判为栈满。答案：B49、若用一个大小为6的数组来实现循环队列，队头指针fkont指向队头元素，队尾指针rear指向队尾元素的下一个位置。若当前rear和front的值分别为。和3,当从队列中删除两个元素，再加入两个元素后，rear和front的值分别为多少？()。A.I 和 5 B.2 和 5 C.4 和 2 D.
27、5 和 1解析：元素出队时，front的公式计算为：front=(front+l)%6,出队两个元素，front的值为5。元素入队时，rear的公式计算为：rear=(rear+l)%6,出队两个元素，rear的值为2。答案：B50、用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时()。A.仅修改队头指针 B.仅修改队尾指针C.队头、队尾指针都要修改 D.队头、队尾指针都可能要修改解析：当队列中有两个或两个以上的结点时，删除操作只修改队头指针，若队列中只有一个结点时，删除操作既要修改队头指针，乂要修改队尾指针。答案:D51、设栈S和队列Q的初始
28、状态为空，元素c l,c2,c3,c4,c5和c6依次通过栈S,个元素出栈后即进队列Q,若6个元素出队的序列是e2,e4,e3,e6,e5,e l,则栈S的容量至少应该是()。A.6 B.4 C.3 D.2解析：出队序列就是出栈序列，得到出栈序列e 2,e 4,e 3,e 6,e 5,e l的过程是：e l,e 2进栈，栈中有2个元素，e 2出栈，栈中有1个元素；e 3、e 4进栈，栈中有3个元素，e 4出栈，e 3出栈，栈中有1个元素；e 5、e 6进栈，栈中有3个元素，e 6出栈，e 5出栈，栈中有1个元素；e l出栈，栈空。由此可知，栈中最多有3个元素，所以栈S的容量至少应该3。答案：C
29、5 2、若串S=s t r u c t u r e”，其子串的数目是().A.9 B.4 6 C.4 5 D.1 0解析：子串是串中任意个连续的字符组成的子序列，并规定空串是任意串的子串，任意串是其自身的子串。若字符串长度为n (n 0),长度为n的子串有1个，长为n-l的子串有2个，长为n-2的子串有3个，长 为1的子 串 有n个。由此可知，长 度 为n的字符串的子串数为n(n+l)/2+1 o所以本题的答案为：9*(9+1)/2+1=4 6.答案：B5 3、已知个稀疏矩阵的三元组表如下：(1,2,3),(1,6,1),(3,1,5),(3,2,-1),(4,5,4),(5,1,-3)则其转
30、置矩阵的三元组表中第3个三元组为()。A.(2,1,3)B,(3,1,5)C,(3,2,-1)D.(2,3,-1)解析：采用三元组存储结构，实现稀疏矩阵转诩的方法是：对给定的三元组表，按列标值升序排序，若列表值相同，再按行标值升序排序；交换行标和列标值。本题中，按此方法得到转置矩阵的三元组表为：(1,3,5),(I,5,-3),(2,1,3),(2,3,-1),(5,4,4),(6,1,1)转置矩阵的三元组表中第 3 个三元组为(2,1,3).答案：A5 4、设有一个1 0阶对称矩阵A,采用压缩存储方式，以行序为主序存储，为第一个元素，其存储地址为1,每个元素占一个字节，则a 8 5 的地址为
31、A.1 3 B.3 3 C.1 8 D.4 0解析：若一个n阶对称矩阵A的卜.标卜界均为0,以行序为主序压缩存储，每个元素占用的字节数为L,则 元 素 的 地 址 为：LOC(aiiJ)=WC(a00)+(/(/+1)/2+j)*L若下标下界不为o,先将下标下界调整为o,然后根据上面公式计算相应元素地址即可。本题中，下标下界都是1,先将下标下界都调整为0,a 8 5 调整为a 7 4,然后计算a 7 4 的地址即可。LOC(a74)=1 +(7*(7+1)/2+4)*1 =1 +32=33答案:B5 5、广义表(a,b,c,d)的表头是().A.a B.()C.(a,b,c,d)D.(b,c,
32、d)解析：根据表头的定义，广义表a,b,c,d)的表头为(a,b,c,d)。答案：C5 6、广义表(a(b,c),d,e)的表尾是()。A.(b,c),d,e)B.a,(b,c)C.(a,(b,c)D.(a)解析：根据表尾的定义，广义表(a,(b,d,e)的表尾为(b,c),d,e)。答 案:A5 7、表头和表尾均为空表的广义表是()。A.()B.()C.()D.();()解析：设L是一个表头和表尾都为的空广义表，即hea d(L)=(),t a i I(L)=(),根据表头和表尾的定义可得：L=()答案：B5 8、设广义表1=(a,b,c),则L的长度和深度分别为()。A.1 和 1 B.1
33、 和 3 C.1 和 2 D.2 和 3解析：广义表的长度是广义表中元素的个数，广义表的深度是广义表中括号嵌套的最大数。依据定义，L的长度为1,深度为2。答案：C5 9、已知广义表L=(x,y,z),a,(u t,w),从L表中取出原子项t的运算是()。A.hea d(t a i l(t a i l(L)B.t a i l(hea d(hea d(t a i l(L)C.hea d(t a i l(hea d(t a i l(L)D.hea d(t a i l(hea d(t a i l(t a i l(L)解析：(1)在L的表尾,取出L的表尾:L l=t a i l(L)=(a,(u,t,w
34、)(2)t 在 L I 的表尾，取出 L 1 的表尾:L 2=t a i l(L l)=(u,t,w)(3)t在L2的表 头,取出L2的表头:L 3=hea d(L 2)=(叩,w)(4)t在L3的表尾，取出L3的表尾:L 4=t a i l(L 3尸(t,w)(5)t是L4的表头,取出L4的表头：hea d(L 4)=t由 止 匕 可 知：t=hea d(L 4)=hea d(t a i l(L 3)=hea d(t a i l(hea d(L 2)=hea d(t a i l(hea d(t a i l(L 1 )=hea d(t a i l(hea d(t a i l(t a i l(L
35、)答案：D6 0、广义表(),()的深度为()oA)0 B)1 C)2 D)36 1、一个n Xn阶的对称矩阵采用压缩存储时需要的存储单元数为()。A)n2B)2 n C)n*(n+l)/2 D)n*(n+1)6 2、下 面()不是顺序表的特点。A)逻辑上相邻的元素，存储在计算机中相邻的存储空间B)在顺序表中查找一个元素与表中元索的分布没有关系C)用动态-维数组存储顺序表最合适D)插入一个元素，平均要移动表长一半的数据元素6 3、f br(i=0;i m;i+)f br O=0;j ncx t=p-ncx t-ncx t B)p=p-ncx tC)p=p-nex t-nex t D)p-nex
36、 t=p6 6、一个栈的入栈序列是a、b、c、d、e,则栈的输出序列不可能是()。A)d cea b B)d ecba C)ed cba D)a bcd e三、填空题1、稀疏矩阵一一般的压缩存储方法有三元组表和()。十字链表2、为了避免造成假溢出现象，经常将顺序队列改造成。解答：为了避免造成假溢出现象，经常将顺序队列改造成循环队列。3、二叉树的第i层(根结点为第1层)上，最多有()个结点。24、有n个结点的完全二叉树(空二叉树的深度为0),其深度h=()o riog2nj+15、广义表 L=(5,(3,2,(14,9,3),(),4),2,(6,3,10)的深度为().36、执行 delete
37、(ABCDEFGHIJ,5,3)后，主串的值为。解答：delete(s,ij)的功能是在串s中删除从第i个字符开始的长度为j的子串。主串的值为ABCDHIJ”7、将插入限定在表的一端，而删除限定在表的另一端进行的线性表称为队列，允许插入的一端称为队尾8、所有插入和删除都在表的一端进行的线性表称为()。栈9、()可以作为实现递归函数调用的种数据结构。栈10、串是一种特殊的线性表，串常见的存储结构有顺序存储和()两种方式。族式仃小11、通常把队列中允许插入的一端称为()。队尾12、设顺序表有19个元素，第一个元素的地址为2 0 0,且每个元素占3个字节，则第14个元素的存储地址 为(239)。第1
38、4个元素的卜.标为1 3,所以第14个元素的存储地址为：200+3*13=23913、已知h是一个带头结点的双链表，每个结点有四个成员：指向前驱结点的指针prior、指向后继结点的指针next、存放数据的成员data和访问频度freq。所有结点的freq初始值为0。每当在双链表上进行一次locate(h,x)操作时，令元素值为x的结点的freq的值增1,并使此链表中结点保持按访问频度递减的顺序排列，以便使访问频度高的结点总是靠近表头。locate(dlink*h,ElemType x)dlink*p=h-next,*q;while(p!=NULL&)p=p-next;p-data!xif(p=
39、NULL)return 0;else p-freq+；q=p-prior;whilc(q!=h&)q-frcq-p-freqp-prior=q-prior;p-prior-next=p;q-next=p-next;if()q-next-prior=q;q-ncxt!NULLp-next=q;q-prior=p;q=p-prior)return 1;)14、下列函数的功能是实现将带头结点单链表的结点值按升序排序，请对程序进行填空。void sort2(slink*11)slink*p,*q,*r,*s;P=H;whilc(p-next!=NULL)q=p-next;r=p;whilc()q-nc
40、xt!NULLif(q-next-datanext-data)r=q;qq-ncxtiR)!=Ps=r-next;r-next=s-next;s-next=p-next;p-next=s;p=p-next15、下列函数的功能是实现带头结点的单链表逆置，请对程序进行填空。void tum(slink*L)slink*p,*q;p=;L-nexlL-next=NULL;while()p-next!=NLLLq=p;p=;p-nextq-next=L-next;L-next=;q16、已知氏度为len的线性表L 采用顺序存储结构。卜.列算法的功能是删除线性表L 中所有值为item的数据元素。type
41、def int ElemType;typedef struct ElemType*data;int length;int listsize;/存储空间基地址*/*顺序表长度（即已存入的元素个数）*/*当前存储空间容量（即能存入的元素个数）*/Jsqlist;void delnode(sqlist*L,ElemType item)int k=0,i=0;while(ilength)if(L-datai=itcm);k+elseL-datai-k=L-datai;L-lcngth=L-lcngth-k;)17、下面程序段为删除带头结点的单循环链表中第个data域值等于x 的结点，请对程序进行填空。
42、Delete(slink*head,int x)slink*p,*q;/*p指向当前处理的结点,q 指向p 的前驱结点*/if(!head)retumO;/*链表为空*/iflhcad-next=hcad)/*链表只有个结点*/ifhead-data=x)frcc(hcad);hcad=NULL;return x;return 0;p=head;q=head;while(q-next!=head)q=;q-nextwhile(p-next!=head)if(p-data=x);q-next=p-nextif(p=head)head=;p-nextfree(p);retum x;)else q=
43、p;p=p-nextreturn 0;)18、卜.列函数的功能是实现将一个带头结点单链表L中所有值为偶数的结点放在所有值为奇数的结点的前面，请对程序进行填空。void ChangeList(slink*L)/*借助于头插法思想*/slink*p,*q；p=L;/*p为q的前驱*/q=L-next;/*用q从头至尾扫描单链表L*/w hile()q!=NULLif(q-data%2=0)p-next=q-next;q-ncxt=;L-ncxtL-next=q;q=;p-ncxt)else;p=qq=q-ncxt;)19、下列函数的功能是实现将一个带头结点单链表L中所有值为x的结点删除，请对程序进
44、行填空。void DclListX(slink*L,ElcmTypc x)slink*p,*q,*t;p=L;/*p为q的前驱*/q=；/*用q从头至尾扫描单链表L*/L-nextwhile(q!=NULL)iR)q-data=xp-next=q-ncxt;free(q);q=p-ncxtelse;p=qq=q-next;四、应用题1、已知广义表L=(a,b,c),(d,e,f,g),给出用取表头(head)和取表尾(ta il)函数取出原子e 的运算。2、画出广义表(a,(b,(c,(),(d,e)的存储图，并计算其深度。孩子兄弟链表3、已知广义表(a,(b,(a,b),(a,b),(a,b
45、),试完成下列操作：任选一种结点结构，画出该广义表的存储结构图：计算该广义表的表头和表尾。计算该广义表的深度。孩子兄弟链表4、已知一棵二叉树的后序遍历序列和中序遍历序列分别为：中序：CBEDAFIGH后序：CEDBIFHGA试画出这棵：叉树，并写出其先序遍历序列.5、已知一棵二叉树的先序遍历序列和中序遍历序列分别为：先序：ABCDEFG中序：CBEDAFG试画出这棵二叉树。并写出其后序遍历序列。6、已知一棵二叉树的先序、中序和后序遍历序列分别为：先序：BExKCJADGHI中序：LKxCAJxxFGIH后序：KLXJCEFXXGDB其中有些字母已丢失，清添写完整，并画出此二义树。7、设字符串
46、S=aabaabaabaac,P=aabaac”(1)给出S 和 P 的next值；(2)若 S 作主串，P 作模式串，试给出利用Brute-Force算法和KMP算法的匹配过程。8、画出下列广义表(0人,(13,9刀,任下)的两种存储结构图。五、算法设计题1、编写算法，按矩阵格式输出按行序压缩存储的n 阶上三角矩阵。2 已知链串类型名为linkstr,编写算法void firstupr(linkstr*s),实现将链串中存放的个英文句子的各单词的首字母变为大写。答案：四、应用题1、答：hcad(tail(head(tail(L)2、答：0 c1 A A该广义表的深度为4。3、答：该广义表的一
47、种存储结构如下:该广义表的表头为a,表 尾 为(b,(a,b),(a,b),(a,b)。该广义表的深度为3。4、答：该二叉树如下:该二叉树的先序序列为:ABCDEGFIHo5、答：该二叉树如下:6、答：先序：BELKCJADGFHI中序：LKECAJBDFGIH后序：KLAJCEFIHGDB该二叉树如下：7、解析：next 的计算方法是：v oid get next(s t r ing*t,int next)/*由模式串 t 求出 next 值*/int j,k;j=O;k=-l;next 0=-l;while(jlengt h)if(k=-l|t-chj=t-chk)j+；k+;next j
48、=k;els e k=next k;(1)S 的 next 值如下:j0 1 23456789 1 0 1 1S 串a a baabaabaacnext j-1 0 1012345678T 的 next 值如下：J0 1 2 3 4 5p串aabaacnext j-10 1 0 1 2(2)利用BF 算法的匹配过程:第一趟匹配：aabaabaabaacaabaac(i=6,j=6)第二趟匹配：aabaabaabaacaa(i=3,j=2)第三趟匹配：aabaabaabaaca(i=3,j=l)利用KMP算法的匹配过程：第一趟匹配：aabaabaabaacaabaac(i=6,j=6)第二趟匹配
49、：aabaabaabaac(aa)baac第三趟匹配：aabaabaabaac(成功)(aa)baac第四趟匹配：aabaabaabaacaabaac(i=9,j=6)第五趟匹配：aabaabaabaacaa(i=6,j=2)第六趟匹配：aabaabaabaaca(i=6,j=l)第七趟匹配：aabaabaabaac(成功)aabaac(i=1 3,j=7)8、答：(1)广义表()人,出,(3 旦),出下)的头尾表示法如图1 所示。图1广义表()人,出,(3丁),田F)头尾表示法(2)广义表()/,(8,(：,。),也1)的孩子兄弟表示法如图2所示。图2广义表()人,(8,口),也下)孩子兄弟
50、表示法五、算法设计题1 print(int a,int n)(int ij;fbr(i=O;in;i-H-)fbr(j=O;jvn;j+)if(inext;whilc(p!=NULL)ifp-ch 1)word=0;else if(word=0)if(p-ch=,a,&p-chch-=32;word=l;p=p-next;一、判断题1、度为2的树就是二叉树。（x）2、完全二叉树一定存在度为1的结点。（x）3、由树转换成二叉树，其根结点的左子树总是空的。x4、完全二叉树中，若一个结点没有左孩子，则它必是叶子结点。（Y）5、二叉树只能用二叉链表表示。（x）6、给定一棵树，可以找到唯一的一棵二叉树与