数据结构应用题答案2014-7-6
数据结构应用题答案
第2章线性表
1.设指针变量p指向双向链表中结点A，指针变量q指向被插入结点B，要求给出在结点A 的后面插入结点B的操作序列（设双向链表中结点的两个指针域分别为llink和rlink）。答：操作序列如下：q->rlink = p->rlink ; p->rlink = q ;
q->rlink->llink = q ; q->llink = p ;
注意答案不唯一
第3章栈和队列
1.设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序。
答：共计14种，分别是：1234， 1243， 1324， 1342， 1432， 2134， 2143， 2341， 2314，2431， 3214， 3241， 3421， 4321
2.如果输入序列为1，2，3，4，5，6，试问能否通过栈结构得到以下两个序列：4，3，5，6，1，2和1，3，5，4，2，6；请说明为什么不能或如何才能得到。
答：（1）不能得到4，3，5，6，1，2 ；因为1，2，3，4入栈后；4，3出栈；得到序列4，3；栈中还有1，2；5入栈后即出栈，得到序列4，3，5；6入栈后即出栈，得到序列4，3，5，6；此时，栈中还有1，2；必须2先出栈，然后1再出栈，1不可能在2之前出栈。故而得不到该序列。
（2）能得到输出顺序为1，3，5，4，2，6的序列。得到的操作如下：1入栈后即出栈，得到序列1；2，3入栈后3即出栈，得到序列1，3；4，5入栈后，5出栈，4出栈，得到序列1，3，5，4；2出栈，得到序列1，3，5，4，2；6入栈后即出栈，得到序列1，3，5，4，2，6。
3.假设正读和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’和‘ababab’则不是回文。假设一字符序列已存入计算机，请用堆栈判断其是否为回文，简述算法。
答：方法一：使用数据结构:循环队列和顺序栈。算法思路为：
1.将字符串按照用户输入的顺序分别入栈和队列
2.分别从队列和栈中取出首个字符
3.比较取出的字符，若相等，继续分别从队列和栈中取首个字符；否则跳出循环，并设置标志flag=0;
4.若队列和栈中的字符都取完，则结束，设置标志flag=1;
5.flag=1,表示字符从前往后和从后往前的序列完全匹配，该字符串属于回文
6.flag=0,表示字符从前往后和从后往前的序列不完全匹配，该字符串不属于回文
方法二：使用栈。将字符串的前一半入栈，再依次出栈，与后一半进行比较，若有不等则不是回文；若依次相等，则是回文。
注意：本题要求简答算法思路，并不要求写出具体算法。
4.试写出循环队列判空和判满的条件（队列最大容量为M）。
答：假设循环队列最大存储容量为M
判空：Q.front==Q.rear （1）
判满：（Q.rear+1）%M==Q.front （2）
评分标准：给出（1）和（2）式分别得3分，其他酌情扣分。
5.假设Q[0..10]是一个循环队列，初始状态为front=rear=0，画出做完下列操作后队列的头尾指针的状态变化情况，若不能入队，请指出其元素，并说明理由。
d,e,b,g,h入队；d,e出队；i,j,k,l,m入队；n,o,p入队
答：（图自己根据解答画出）d,e,b,g,h入队；状态1：front=0，rear=5；
d,e出队；状态2：front=2，rear=5；
i,j,k,l,m入队；状态3：front=2，rear=10；
n,o,p入队；状态4：front=2，rear=1；p不能入队，因为队列已经满了。
评分标准：状态1、状态4各2分，状态2、状态3各1分，状态4中状态1分，理由1分。
6.若元素的进栈序列为：A、B、C、D、E，运用栈操作，能否得到出栈序列B、C、A、E、D和D、B、A、C、E？为什么？
答：能得到出栈序列B、C、A、E、D，不能得到出栈序列D、B、A、C、E。其理由为：若出栈序列以D开头，说明在D之前的入栈元素是A、B和C，三个元素中C是栈顶元素，B和A不可能早于C出栈，故不可能得到D、B、A、C、E出栈序列。
7.设输入序列为a,b,c,d,试写出借助一个栈可得到的两个输出序列和两个不能得到的输出序列。
答：借助栈结构，n个入栈元素可得到1/(n+1)((2n）！/（n!*n!）)种出栈序列。本题4个元素，可有14种出栈序列，abcd和dcba就是其中两种。但dabc和adbc是不可能得到的两种。
8.将两个栈存入数组V[1..m]应如何安排最好？这时栈空、栈满的条件是什么？
答：设栈S1和栈S2共享向量V[1..m]，初始时，栈S1的栈顶指针top[0]=0，栈S2的栈顶指针top[1]=m+1，当top[0]=0为左栈空，top[1]=m+1为右栈空；当top[0]=0并且top[1]=m+1时为全栈空。当top[1]-top[0]=1时为栈满。
9.如果输入序列为1 2 3 4 5 6,试问能否通过栈结构得到以下两个序列:4 3 5 6 1 2和1 3 5 4 2 6；请说明为什么不能或如何才能得到。
答：输入序列为123456，不能得出435612，其理由是，输出序列最后两元素是12，前面4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能栈底元素1在栈顶元素2之前出栈。
得到135426的过程如下：1入栈并出栈，得到部分输出序列1；然后2和3入栈，3出栈，部分输出序列变为：13；接着4和5入栈，5，4和2依次出栈，部分输出序列变为13542；最后6入栈并退栈，得最终结果135426。
10.假设以数组sq[0..7]存放循环队列元素,变量f指向队头元素的前一位置,变量r指向队尾元素，如用A和D分别表示入队和出队操作，请给出：
（1）队空的初始条件；
（2）执行操作序列A3 D1 A5 D2 A1 D2 A4时的状态,并作必要的说明。（A3表示三次入队操作，D1表示一次出队操作）
答：（1）队空的初始条件：f=r=0；
（2）执行操作A3后，f=0，r=3；//A3表示三次入队操作
执行操作D1后，f=1，r=3；//D1表示一次出队操作
执行操作A5后，f=1，r=0；
执行操作D2后，f=3，r=0；
执行操作A1后，f=3，r=1；
执行操作D2后，f=5，r=1；
执行操作A4后，按溢出处理。因为执行A3后，r=4，这时队满，若再执行A操作，则出错。
11.内存中一片连续空间（不妨假设地址从1到m）提供给两个栈S1和S2使用，怎样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢1
答： S1和S2共享内存中一片连续空间（地址1到m），可以将S1和S2的栈底设在两端，两栈顶向共享空间的中心延伸，仅当两栈顶指针相邻（两栈顶指针值之差的绝对值等于1）时，判断为栈满，当一个栈顶指针为0，另一个栈顶指针m+1时为两栈均空。
12.设一数列的输入顺序为123456，若采用堆栈结构，并以A和D分别表示入栈和出栈操作，试问通过入出栈操作的合法序列。
（1）能否得到输出顺序为325641的序列。
（2）能否得到输出顺序为154623的序列。
答：（1）能得到325641。在123依次进栈后，3和2出栈，得部分输出序列32；然后4，5入栈，5出栈，得部分出栈序列325；6入栈并出栈，得部分输出序列3256；最后退栈，直到栈空。得输出序列325641。其操作序列为AAADDAADADDD。
（2）不能得到输出顺序为154623的序列。部分合法操作序列为ADAAAADDAD，得到部分输出序列1546后，栈中元素为23，3在栈顶，故不可能2先出栈，得不到输出序列154623。
13.设输入序列为2，3，4，5，6，利用一个栈能得到序列2，5，3，4，6吗？为什么？栈可以用单链表实现吗？
答：不能得到序列2，5，3，4，6；其理由是，输出序列第三四位两元素是3，4，前面2个元素（2，5）得到后，栈中元素剩3，4，且4在栈顶，栈底元素3不可能在栈顶元素4之前出栈。
栈可以用单链表实现，这就是链栈。由于栈只在栈顶操作，所以链栈通常不设头结点。
14.有5个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D 最先出栈（即C第一个且D第二个出栈）的次序有哪几个？用S表示入栈，X表示出栈，写出可能得到次序的操作序列。
答：三个：CDEBA，CDBEA，CDBAE
CDEBA操作序列：SSSXSXSXXX；CDBEA操作序列：SSSXSXXSXX；CDBAE操作序列：SSSXSXXXSX；
15.若以1、2、3、4作为双端队列的输入序列，试分别求出以下条件的输出序列：
（1）能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列；
（2）能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列；
（3）既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列。答：（1）4132 （2）4213 （3）4231
16.设一个双端队列，元素进入该队列的次序为a，b，c，d。求既不能由输入受限的双端队列得到,又不能由输出受限的双端队列得到的输出序列。
答：既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是dbca。
第6章树和二叉树
1.（8分）已知一棵树的边的集合表示为：(L,N),(G,K),(G,L),(G,M),(B,E),(B,F),(D,G),
(D,H),(D,I),(D,J),(A,B),(A,C),(A,D))画出这棵树，并回答下列问题：
(1)树根是哪个结点？哪些是叶子结点？哪些是非终端结点？
(2)树的度是多少？各个结点的度是多少？
(3)树的深度是多少？各个结点的层数是多少？以结点Ｇ为根的子树的深度是多少？
X72.
答案HIDJKEBLFGCA
X23.（5分）对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，证明：n0=n2+1。
X34.叙述并证明二叉树的性质3。
X35.（8分）已知一棵二叉树如下，
（1）请分别写出按前序、中序、后序和层次遍历时得到的结点序列。
（2）如果此二叉树由森林转换得到，请画出原森林中的各棵树。
X1X56.（8分）画出由下列序列得到的二叉树以及由此二叉树转化的森林：先序：EBADCFHGIKJ；中序：ABCDEFGHIJK。
X87.有二叉树中序序列为：ABCEFGHD，后序序列为：ABFHGEDC，请画出此二叉树，并写出二叉树的先序遍历序列和层次遍历序列。
答案根据后序序列知根结点为C，因此左子树：中序序列为AB 后序序列为AB 右子树：中序序列为EFGHD ，后序序列为：FHGED 依次推得该二叉树结构如下图所示
先序遍历序列：CBADEGFH
层次遍历序列：CBDAEGFH
X58.（8分）二叉树T的前序遍历序列和中次遍历序列分别是ABCDEFG和CBEDAFG，试画出该二叉树，并写出二叉树的后序遍历序列和层次遍历序列。
X99.（6分）二叉树的先序序列为EBADCFHGIKJ；二叉树的中序序列为ABCDEFGHIJK，请画
出该二叉树，并写出二叉树的后序遍历序列和层次遍历序列。
X1010.（8分）设一棵二叉树的先序、中序遍历序列分别为
先序遍历序列： A B D F C E G H 中序遍历序列： B F D A G E H C
请画出该二叉树，并将这棵二叉树转换成对应的树（或森林）。
X411.（8分）设一棵二叉树的前序序列为ABDGECFH，中序序列为：DGBEAFHC 。试画出该二叉树。并写出后序和层次遍历序列。
12.（6分）设给定一个权值集合W=(3，5，7，9，11)，要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度WPL。
X613.（8分）假设字符a,b,c,d,e,f,g,h的使用频度分别是
0.15,0.19,0.07,0.08,0.04,0.23，0.13，0.11画出哈夫曼树并写出a,b,c,d,e,f,g,h的Huffman（哈夫曼）编码。
X514.（8分）假设字符a,b,c,d,e,f的使用频度分0.07,0.09,0.12,0.22,0.23,0.27，写出a,b,c,d,e,f的Huffman（哈夫曼）编码。
X715.（8分）假设字符a,b,c,d,e,f的使用频度分别是0.07,0.10,0.12,0.16,0.25,0.30，构造哈夫曼树并写出a,b,c,d,e,f的哈夫曼编码。
16.（6分）试分别画出具有三个结点的树和三个结点的二叉树的不同形态。
X617.请画出下图所示的树所对应的二叉树。
答案：
18.（6分）请画出与下列二叉树对应的森林。
X10X819.已知一棵树边的集合为{
x10（1）哪个是根结点？（2）X8哪些是叶子结点？X10哪些是分支结点？X8（3）哪个是结点G的双亲结点？（4）哪些是结点G的祖先？X8（5）哪些是结点G的孩子？
X8（6）哪些是结点E的子孙？X8（7）哪些是结点E的兄弟？哪些是结点F的兄弟？
（8）结点B和N的层次号分别是多少？（9）树的深度是多少？
（10）以结点C为根的子树的深度是多少？
答案（1）A；（2）D, M, N, F, J, K, L； (3) C； (4) A, C； (5) J,K；(6) I, M, N；
(7) E的兄弟是D，F的兄弟是G和H；（8）2, 5； (9) 5； (10) 3。
X920.假设在树中，结点x是结点y的双亲时，用（x，y）来表示树边。已知一棵树边的集合为：{（i，m），（i，n），（e，i），（b，e），（b，d），（a，b），（g，j），（g，k），（c，g），（c，f），（h，l），（c，h），（a，c）}。用树形表示法画出此树，并回答下列问题：
（1）哪个是根结点：（2）哪些是叶结点？（3）哪个是g的双亲？
（4）哪些是g的祖先？（5）哪些是g的孩子？（6）哪些是e的子孙？
（7）哪些是e的兄弟？哪些是f的兄弟？（8）结点b和n的层次各是多少？
（9）树的深度是多少？（10）以结点c为根的子树的深度是多少？
（11）树的度数是多少？
答案：
（1）根结点：a （2）叶结点：m、n、d、l、h、j、k （3）g的双亲：c
（4）g的祖先：a、c （5）g的孩子：j、k （6）e的子孙：i、m、n
（7）e的兄弟：d （8）b的层次：2 （9）树的深度：5 f的兄弟：g、hn的层次；5
（10）以结点c为根的子树的深度：3 （11）树的度数：3
21.已知一棵树边的结点为（I,M），(I，N),(E，I),(B，E)，(B，D),(C，B),(G，L)，(G，K)，(A，G)，(A，F),(H，J)，(A，H)，(C，A)}，试画出这棵树，并回答下列问题：
(1)哪个是根结点？
(2)哪些是叶子结点？
(3)树的深度是多少？
答案如下图所示。（图不对，缺结点H的孩子结点J，）
根结点C，叶子结点F、K、L、J、D、M、N，深度5
五、应用题（每小题6分，共48分）
3.答：快速排序的思想：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
评分标准：只要基本思想对就可得分。
3、（8分）二叉树为：
后序遍历序列：CEDBGFA，层次遍历序列：ABFCDGE
评分标准：得出二叉树得4分，给出后序和层次遍历序列得4分，步骤不全酌情给分。
4、（8分）哈夫曼树：
哈夫曼编码：
a：011 b：10 c：00000 d：0010
e：0001 f：11 g：001 h：0101
评分标准：得出哈夫曼树给4分，给出哈夫曼编码给4分，步骤不全酌情给分。
5、（10分）
（1）邻接表存储结构
（2）深度优先遍历序列：BADCEF
广度优先遍历序列：BACEDF
评分标准：画出邻接表存储结构得5分，求出深度优先和广度优先遍历序列得5分，其他情况全酌情给分。
6、（8分）二叉判定树
平均查找长度：ASL=（1+2*2+4*3+3*4）/10=2.9
评分标准：得出二叉判定树给6分，求出平均查找长度给2分，步骤不全酌情给分。
2、（6分）快速排序的思想：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
评分标准：只要基本思想对就可得分。
3、（8分）二叉树为：
后序遍历序列：CEDBGFA，层次遍历序列：ABFCDGE
评分标准：得出二叉树得4分，给出后序和层次遍历序列得4分，步骤不全酌情给分。
4、（8分）哈夫曼树：
哈夫曼编码：
a：011 b：10 c：00000 d：0010
e：0001 f：11 g：001 h：0101
评分标准：得出哈夫曼树给4分，给出哈夫曼编码给4分，步骤不全酌情给分。
5、（10分）
（1）邻接表存储结构
（2）深度优先遍历序列：BADCEF
广度优先遍历序列：BACEDF
评分标准：画出邻接表存储结构得5分，求出深度优先和广度优先遍历序列得5分，其他情况全酌情给分。
6、（8分）二叉判定树
平均查找长度：ASL=（1+2*2+4*3+3*4）/10=2.9
评分标准：
得出二叉判定树给
6分，求出平均查找长度给
2分，步骤不全酌情给分。 四、算法题（22分） 1、（6分）
评分标准：每写错一种形态扣1分。 2、（8分）
（1）前序：ABDGCEFH 中序：DGBAECHF 后序：GDBEHFCA 层次：ABCDEFGH （2）二叉树所对应的森林：
评分标准：第一小题每个1分，第二小题三棵树4分，每错一个扣1分。
3、（8分）二叉排序树的构造过程如下：
评分标准：没有过程或过程不全酌情减分
4、
（8分）
评分标准：结果正确得5分，步骤不全酌情扣分。
5、（10分）
（3）（2分）平均查找长度：
ASL sc =（6*1+2+3*3+6）/11=23/11 6、（8分）
（36）25 48 12 65 20 （25 36）48 12 65 20 （25 36 48）12 65 20
（12 25 36 48）65 20 （12 25 36 48 65）20 （12 20 25 36 48 65）
评分标准：每一趟插入得1分，步骤不全酌情扣分。 三、应用题（
43分）
1、（6分）对任何一棵二叉树，如果其终端结点数为n 0，度为2的结点数为n 2，则n 0=n 2+1。
证明：设二叉树的结点总数为n ，度为1的结点个数为n 1，则有： n=n 0+n 1+n 2 （1）
又在二叉树中除了根结点每个结点都有一个分支指向它，这些分支是有度为1
和度为2的结点发出的，由此得到： n-1=n 1+2*n 2 （2） 由式（1）和（2）得n 0=n 2+1，证毕。
评分标准：叙述定理得2分，证明得4分，其他酌情扣分。 2、（8分）哈夫曼树为：
由此可得哈夫曼编码分别为： a ：000 b ：001 c ：100 d ：101 e ：01 f ：11
评分标准：得出哈夫曼树给4分，给出哈夫曼编码给4分，步骤不全酌情给分。 3、（8分）二叉排序树的构造过程如下：
分
平均查找长度：ASL=（1+2*2+4*3+2*4+5）/10=3 3分
评分标准：得出二叉判定树给5分，求出平均查找长度给3分，步骤不全酌情给分。 4、（7分）拓扑序列构造过程
输出输出
输出C 输出D
拓扑有序序列有两种：ABCDEF 和ACBDEF
评分标准：只有结果没有过程给5分，过程不全或过程不正确酌情扣分。 5、（8分）邻接矩阵为
?
?
????
?
??
?
?
??0010100
000011100011000010100111101001001010100010
最小生成树为：
评分标准：写出邻接矩阵给3分，最小生成树给5分，只有结果没有过程给3分，过程不全或过程不正确酌情扣分。
6、（6分）快速排序的思想：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
一趟快速排序的结果：40，38，27，20，13，49，76，80，65
评分标准：写出快速排序思想给3分，给出一趟排序结果给3分。
四、算法题（22
分）
三、应用题（43分）
1、（6分）
3分
3分
评分标准：构造出二叉树得3分，二叉树的生成森林得3分。 2、（8分）
分 平均查找长度：ASL=（1+2*2+4*3+3*4）/10=2.9 3分
评分标准：得出二叉判定树给4分，求出平均查找长度给2分，步骤不全酌情给分。 3、（7分）邻接矩阵：
??????
????
? ??∞∞
∞
∞
∞
∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞
3
7
6238837635512
13分 深度优先序列：abcdehf 或abchedf 或abcfdeh 或abcfhed （不唯一）2分 广度优先序列：abfcdhe 或afbcdhe 或abfchde 或afbchde （不唯一）2分
评分标准：写出图的邻接矩阵的2分，深度优先序列得2分，广度优先序列得2分，其他酌情给分。 4、（8分）最短路径：
评分标准：最短路径给5分，过程给3分，结果正确没有过程或过程不对酌情减分。 5、（8
ASL sc=（6*1+2+3*3+4）/11=21/11
评分标准：写出哈希表得5分，查找长度3分
6、（5分）
（1）是大顶堆
（2）不是堆，调整以后为100，98，66，85，80，60，40，77，82，10，20
（3）是小顶堆
评分标准：判断正确得3分，调整得3分
四、算法题（22分）
1、（5分）假设循环队列最大存储容量为M
判空：Q.front==Q.rear （1）
判满：（Q.rear+1）%M==Q.front （2）
评分标准：给出（1）和（2）式分别得2分，前提假设得1分，其他酌情扣分。
2、（5分）对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。
证明：设二叉树的结点总数为n，度为1的结点个数为n1，则有：
n=n0+n1+n2（1）
又在二叉树中除了根结点每个结点都有一个分支指向它，这些分支是有度为1
和度为2的结点发出的，由此得到：
n-1=n1+2*n2（2）
由式（1）和（2）得n0=n2+1，证毕。
评分标准：给出（1）和（2）式分别得2分，得出结论得1分，其他酌情扣分。
3、（7分）哈夫曼树为：
由此可得哈夫曼编码分别为：
a：000 b：001 c：100
d：101 e：01 f：11
评分标准：得出哈夫曼树给4分，给出哈夫曼编码给3分，步骤不全酌情给分。
4、（8分）二叉排序树：
平均查找长度：ASL=（1+2*2+3*3+4*3+5*2+6）/12=3.5
评分标准：构造出二叉排序树得5
分，平均查找长度得3分，步骤不全酌情扣分。 5、（7分）
由C 开始的深度优先生成序列：CDEABF
评分标准：画出原图得4分，求出深度优先生成序列得3分，其他情况酌情给分。 6、（8分）最短路径求解过程：
五、算法题（共20分） 1、（5分）
评分标准：每写对一种形态得1分。
2、（5分）快速排序的思想：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
评分标准：只要基本思想对就可得分。
3、（7分）
（1）前序：ABDGCEFH 中序：DGBAECHF 后序：GDBEHFCA 层次：ABCDEFGH
（2）二叉树所对应的森林：
评分标准：第一小题每个1分，第二小题三棵树，每个1分。
4、（8分）关键路径为：
求解过程：
5、（8分）最小生成树为：
评分标准：结果正确没有过程给5分，过程不全或过程不正确酌情扣分。
6、哈希表：
ASL sc=（6*1+2+3*3+4）/11=21/11
评分标准：写出哈希表得5分，查找长度2分，其他情况酌情给分。五、算法题（20分）
四、应用题（40分）
1、（8分）
4分
4分
评分标准：构造出二叉树得4分，二叉树的生成森林得4分。
2、（8分）二叉排序树的构造过程如下：
评分标准：没有过程或过程不全酌情减分
3、（8分）邻接矩阵：
??????
????
? ??∞∞
∞
∞
∞
∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞3
7
6238837635512
14分 深度优先序列：abcdehf 或abchedf 或abcfdeh 或abcfhed （不唯一） 广度优先序列：abfcdhe 或afbcdhe 或abfchde 或afbchde （不唯一）4分 评分标准：写出图的邻接矩阵的4分，深度优先序列得2分，其他酌情给分。 4、（8分）
3．
评分标准：最小生成树给4分，过程给4分，结果正确没有过程或过程不对酌情减分。 5、（8分）哈希表：
ASL sc =（7*1+2+3+3）/10=1.5
评分标准：写出哈希表得5分，查找长度3分
最新版数据结构1800题含完整答案详解
数据结构1800例题与答案 第一章绪论 一、选择题（每小题2分） 1．算法的计算量的大小称为计算的（ B ）。【北京邮电大学2000 二、3 （20/8分）】 A．效率B．复杂性C．现实性D．难度 2．算法的时间复杂度取决于（C）。【中科院计算所1998 二、1 （2分）】 A．问题的规模B．待处理数据的初态C．A和B D．都不是 3．计算机算法指的是（①C ），它必须具备（② B ）这三个特性。 ①A．计算方法B．排序方法 C．解决问题的步骤序列D．调度方法 ②A．可执行性、可移植性、可扩充性B．可执行性、确定性、有穷性 C．确定性、有穷性、稳定性D．易读性、稳定性、安全性【南京理工大学1999 一、1（2分）【武汉交通科技大学1996 一、1（4分）】4．一个算法应该是（B ）。【中山大学1998 二、1（2分）】 A．程序B．问题求解步骤的描述 C．要满足五个基本特性D．A和C. 5．下面关于算法说法错误的是（ D ）【南京理工大学2000 一、1（1.5分）】A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（C ）【南京理工大学2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（ C ）两大类。【武汉交通科技大学1996 一、4（2分）】 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（ D ）。【北方交通大学2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（ D ）？【北方交通大学2001 一、1（2分）】 A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（Ａ）【北方交通大学2001 一、2（2分）】 A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（Ｃ）【北京工商大学2001 一、10（3分）】 FOR i:=1 TO n DO
数据结构专升本模拟题及答案
作业题（一） 一、单项选择题 1. 从逻辑上可以把数据结构分为（）两大类。 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 2. 链表不具有的特点是（） A．插入、删除不需要移动元素B．可随机访问任一元素 C．不必事先估计存储空间D．所需空间与线性长度成正比 3.下面程序段的时间复杂度的量级为（）。 For(i=1;i<=n;i++) For(j=1;j<=I;j++) For(k=1;k<=j;k++) X=x+1; A．O(1) B．O(n) C．O(n2) D．O(n3) 4.在一个带头结点的双向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改（）个指针域的值。 A．2 B．3 C．4 D．6 5、一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是（）。 A．98 B．100 C．102 D．106 6、判定一个栈s（最多元素为m0）为空的条件是（）。 A．s-〉top! =0 B．s-〉top= =0 C．s-〉top! =m0 D．s-〉top= =m0 7、循环队列用数组A[m]（下标从0到m-1）存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（）。 A．（rear-front+m）%m B．rear-front+1 C．rear-front-1 D．rear-front 8、设有两个串S1与S2，求串S2在S1中首次出现位置的运算称作（）。 A．连接B．求子串 C．模式匹配D．判子串 9、设串S1='ABCDEFG'，S2='PQRST'，函数con（x，y）返回x和y串的连接串，subs(s,i,j)返回串S的的从序号i的字符开始的j个字符组成的子串，len(s)返回串S的长度，则con(subs(S1,2,len(S2)),subs(S1,len(S2),2))的结果是（）。
目前最完整的数据结构1800题包括完整答案-第三章-栈和队列范文(汇编)
第3章栈和队列 一选择题 1. 对于栈操作数据的原则是（）。【青岛大学 2001 五、2（2分）】 A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 2. 在作进栈运算时,应先判别栈是否( ① ),在作退栈运算时应先判别栈是否( ② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③ )。 为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的 ( ④ )分别设在这片内存空间的两端,这样,当( ⑤ )时，才产生上溢。①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 ④: A. 长度 B. 深度 C. 栈顶 D. 栈底 ⑤: A. 两个栈的栈顶同时到达栈空间的中心点. B. 其中一个栈的栈顶到达栈空间的中心点. C. 两个栈的栈顶在栈空间的某一位置相遇. D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底. 【上海海运学院 1997 二、1（5分）】【上海海运学院 1999 二、1（5分）】 3. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（）。 A. 不确定 B. n-i+1 C. i D. n-i 【中山大学 1999 一、9(1分)】 4. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（）。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的 【武汉大学 2000 二、3】 5. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，p N,若p N是n，则p i是( )。 A. i B. n-i C. n-i+1 D. 不确定 【南京理工大学 2001 一、1（1.5分）】 6. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 【北方交通大学 2001 一、3（2分）】 7. 设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。【中科院计算所2000一、10(2分)】 A. 1，2，4，3， B. 2，1，3，4， C. 1，4，3，2， D. 4，3，1，2， E. 3，2，1，4， 8. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 【南开大学 2000 一、1】【山东大学 2001 二、4 (1分)】【北京理工大学 2000 一、2（2分）】 9. 设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（）。 A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 4 【合肥工业大学 2001 一、1（2分）】 10. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是
数据结构模拟试题及答案
数据结构模拟试题一 一、判断题（每小题1 分，共15分） 1.计算机程序处理的对象可分为数据和非数据两大类。 2.全体自然数按大小关系排成的序列是一个线性表。 3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。 4.顺序栈是一种规定了存储方法的栈。 5.树形结构中的每个结点都有一个前驱。 6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。 7.若某顶点是有向图的根，则该顶点的入度一定是零。 8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。 9.用一维数组表示矩阵可以节省存储空间。 10.广义表的长度与广义表中含有多少个原子元素有关。 11.分块查找的效率与线性表被分成多少块有关。 12.散列表的负载因子等于存入散列表中的结点个数。 13.在起泡排序过程中，某些元素可能会向相反的方向移动。 14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。 15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。 二、填空题（每空1分，共15分） 1.顺序表是一种_____________线性表。 2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。 3.栈和队列的区别在于________的不同。 4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。 5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域 为空的结点。 6.n个顶点的有根有向图中至少有___条边，至多有___条边。 7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。 8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是 _____。 9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。 10.在高度为3的6阶B-树中，至少有___个关键字，至多有___个关键字。 三、选择题（每题2分，共30分） 1.计算机所处理的数据一般具有某种内在联系性，这是指________。 A．元素和元素之间存在某种关系B．数据和数据之间存在某种关系 C．元素内部具有某种结构D．数据项和数据项之间存在某种关系 2. 假设顺序表目前有4个元素，第i个元素放在R[i]中，1≤i≤4 。若把新插入元素存入R[6]，则________。 A．会产生运行错误B．R[1]~R[6]不构成一个顺序表 C．顺序表的长度大于顺序表元素个数，会降低存储空间利用率 D．顺序表元素序号和数组元素下标不一致，会给使用带来麻烦 3. 设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。当P指向链表最后一个结点时，_________。A．P所指结点指针字段的值为空B．P的值与H的值相等 C．P所指结点的地址与H的值相等D．P所指结点指针字段的值与H的值相等 4. 栈的定义不涉及数据的__________。 A．逻辑结构B．存储结构C．运算D．逻辑结构和存储结构 5. 设5个元素进栈的顺序是1,2,3,4,5，则出栈的顺序有可能是___________。 A．2,4,1,3,5 B．3,4,1,5,2 C．3,2,4,1,5 D．4,1,3,2,5 6. 若某棵二叉树结点的前序序列和中序序列相同，则该二叉树_________。 A．只有一个结点B．每个结点都没有左孩子C．每个结点都没有右孩子D．不存在 7.对于一棵具有n个结点，度为3的树来说，____________。 A．树的高度至多是n-3 B．树的高度至多是n-2 C．树的最低高度是┏log3(n+1)┓ D．至少在某一层上正好有3个结点 8．n个顶点的有向图如果可以进行拓扑排序，则可以断定该有向图__________。 A．含n个强连通分量B．有唯一的入度为0的顶点C．有多个出度为0的顶点 D．是一个有根有向图 9. 特殊矩阵用行优先顺序表表示，_____________ A．简化了矩阵元素之间的逻辑关系B．便于按行处理矩阵元素
数据结构各习题
数据结构各章习题 第1章绪论 一、名词解释 数据数据项数据元素数据结构数据逻辑结构数据物理结构算法算法的时间复杂性 二、单项选择题 1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的①、数据信息在计算机中的②以及一组相关的运算等的课程。 ① A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象 ② A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法 2. 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是①的有限集合，R是D上的②有限集合。 ① A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．数据对象 ② A．操作Ｂ．映象Ｃ．存储Ｄ．关系 3. 在数据结构中，从逻辑上可以把数据结构分成。 A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构 Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构 4. 算法分析的目的是①，算法分析的两个主要方面是②。 ① A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 ② A. 空间复杂性和时间复杂性 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 5.算法指的是。 A. 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法 6. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。 A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 三、填空题（将正确的答案填在相应的空中） 1. 数据逻辑结构包括、、和四种类型 2. 在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。 3. 在树形结构中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子结点没有结点，其余每个结点的直接后续结点可以。 4. 在图形结构中，每个结点的前驱结点数和后续结点数可以。 5. 线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。 6. 算法的五个重要特性是__ __ , __ __ , ___ _ , __ __ , _ ___。 四、分析下列算法的时间复杂度: 1．sum=0;
目前最完整的数据结构1800题包括完整答案树和二叉树答案
第6章树和二叉树 部分答案解释如下。 12. 由二叉树结点的公式：n=n0+n1+n2=n0+n1+(n0-1)=2n0+n1-1，因为n=1001,所以1002=2n0+n1,在完全二叉树树中，n1只能取0或1,在本题中只能取0，故n=501，因此选E。 42.前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树，所以本题的A和B均对，单支树的特点是只有一个叶子结点，故C是最合适的，选C。A或B 都不全。由本题可解答44题。 47. 左子树为空的二叉树的根结点的左线索为空（无前驱），先序序列的最后结点的右线索为空（无后继），共2个空链域。 52．线索二叉树是利用二叉树的空链域加上线索，n个结点的二叉树有n+1个空链域。 部分答案解释如下。 6．只有在确定何序（前序、中序、后序或层次）遍历后，遍历结果才唯一。 19．任何结点至多只有左子树的二叉树的遍历就不需要栈。 24. 只对完全二叉树适用，编号为i的结点的左儿子的编号为2i(2i<=n)，右儿子是2i+1（2i+1<=n） 37. 其中序前驱是其左子树上按中序遍历的最右边的结点（叶子或无右子女），该结点无右孩子。 38 . 新插入的结点都是叶子结点。 42. 在二叉树上，对有左右子女的结点，其中序前驱是其左子树上按中序遍历的最右边的结点（该结点的后继指针指向祖先），中序后继是其右子树上按中序遍历的最左边的结点（该结点的前驱指针指向祖先）。 44．非空二叉树中序遍历第一个结点无前驱，最后一个结点无后继，这两个结点的前驱线索和后继线索为空指针。 三.填空题
1.(1)根结点(2)左子树(3)右子树 2.(1)双亲链表表示法(2)孩子链表表示法(3)孩 子兄弟表示法 3．p->lchild==null && p->rchlid==null 4.(1) ++a*b3*4-cd (2)18 5.平衡 因子 6. 9 7. 12 8.(1)2k-1 (2)2k-1 9.(1)2H-1 (2)2H-1 (3)H=?log2N?+1 10. 用顺序存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，要加“虚结 点”。设编号为i和j的结点在顺序存储中的下标为s 和t ,则结点i和j在同一层上的条 件是?log2s?=?log2t?。 11. ?log2i?=?log2j?12.(1)0 (2)(n-1)/2 (3)(n+1)/2 (4) ?log2n?+1 13.n 14. N2+1 15.(1) 2K+1-1 (2) k+1 16. ?N/2? 17. 2k-2 18. 64 19. 99 20. 11 21.(1) n1-1 (2)n2+n3 22.(1)2k-2+1（第k层1个结点，总结点个数是2H-1，其双亲是2H-1/2=2k-2）(2) ?log2i?+1 23.69 24. 4 25.3h-1 26. ?n/2? 27. ?log2k?+1 28.(1)完全二叉树 (2)单枝树，树中任一结点（除最后一个结点是叶子外）,只有左子女或 只有右子女。 29.N+1 30.(1) 128(第七层满，加第八层１个) (2) 7 31. 0至多个。任意二叉树，度为１的结点个数没限制。只有完全二叉树，度为１的结点个 数才至多为1。 32．21 33.(1)2 (2) n-1 (3) 1 (4) n (5) 1 (6) n-1 34.(1) FEGHDCB (2)BEF（该二叉树转换成森林，含三棵树，其第一棵树的先根次序是 BEF） 35.(1)先序（2）中序 36. (1)EACBDGF （2）2 37.任何结点至多只有右子女 的二叉树。 38.(1)a (2) dbe (3) hfcg 39.(1) . (2) ...GD.B...HE..FCA 40.DGEBFCA 41．(1)5 （2）略 42.二叉排序树 43.二叉树 44. 前序 45.(1)先根次序（2）中根次序46.双亲的右子树中最左下的叶子结点47.2 48.(n+1)/2 49.31（x的后继是经x的双亲y的右子树中最左下的叶结点） 50.(1)前驱 (2)后 继 51.(1)1 (2)y^.lchild (3)0 (4)x (5)1 (6) y (7)x(编者注：本题按 中序线索化) 52.带权路径长度最小的二叉树，又称最优二叉树 53.69 54.(1)6 (2)261 55.(1)80 (2)001（不唯一）56.2n0-1 57.本题①是表达式求值，②是在二叉排序树中删除值为x的结点。首先查找x，若没有x， 则结束。否则分成四种情况讨论：x结点有左右子树；只有左子树；只有右子树和本身是叶 子。 (1)Postoder_eval(t^.Lchild) (2) Postorder_eval(t^.Rchild) (3)ERROR(无此运 算符)(4)A (5)tempA^.Lchild (6)tempA=NULL(7)q^.Rchild (8)q (9)tempA^.Rchild (10)tempA^.Item 一．是非题 1. 数据结构(应该是抽象数据类型)可用三元式表示(D，S，P)。其中：D是数据对象，S是D上的关系，P是对D的基本操作集。(f) 2 简单地说,数据结构是带有结构的数据元素的集合。(t) 3 判断带头结点的非空循环单链表(头指针为L)中指针p所指结点是最后一个元素结点 的条件是：p->next==L。(t) 4 线性表的链式存储结构具有可直接存取表中任一元素的优点。(f) 5 线性表的顺序存储结构优于链式存储结构。(f) 6. 在单链表P指针所指结点之后插入S结点的操作是： P->next= S ; S-> next = P->next;。(f) (顺序弄反了S-> next = P->next; P->next= S ;) 7 对于插入、删除而言，线性表的链式存储优于顺序存储。(t) 8. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(f) 9. 栈和队列是操作上受限制的线性表。(t) 10. 队列是与线性表完全不同的一种数据结构。(f) (栈和队列是操作上受限制的线性表) 11. 队列是一种操作受限的线性表，凡对数据元素的操作仅限一端进行。(f) (两端) 12. 栈和队列也是线性表。如果需要，可对它们中的任一元素进行操作。(f) ( “如果需要,可对它们中的任一元素进行操作.” 这里的意思是在O(1)的时间来读和改某个元素。比如数组的直接索引。 栈：如果需要，每一次只能对栈顶的元素进行操作 队列：如果需要，每一次只能对两端，或者只能对队列头的元素进行操作。) 13. 栈是限定仅在表头进行插入和表尾进行删除运算的线性表。(f) 14. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。(f) (二叉树和树相互独立) 15 二叉树是一棵结点的度最大为二的树。(f) (二叉树和树相互独立) 16 赫夫曼树中结点个数一定是奇数。(t) 17 在二叉树的中序遍历序列中，任意一个结点均处在其左孩子结点的后面。(t) (LDR) 18 假设B是一棵树，B′是对应的二叉树。则B的后根遍历相当于B′的后序遍历。(f) (后根遍历相当于中序遍历) 19. 通常，二叉树的第i层上有2i-1个结点。(f) (应该为1~2i-1个) 20. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。(t) 21 二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。(t) 22 由树结点的先根序列和后根序列可以唯一地确定一棵树。(t) 23 邻接多重表可以用以表示无向图，也可用以表示有向图。(f) (只能表示无向图，有向图用十字链表) 24 可从任意有向图中得到关于所有顶点的拓扑次序。(f) (带环图没有) 25 有向图的十字链表是将邻接表和逆邻接表合二为一的链表表示形式。(t) 2013-2014学年二学期数据结构期末考试模拟试卷(1~6卷) 一、应用题(3小题，共24分) 1已知某字符串S中共有8种字符，各种字符分别出现2次、1次、4次、5次、7次、3 次、4次和9次，对该字符串用［0,1］进行前缀编码，问该字符串的编码至少有多少位。 【解答】以各字符出现的次数作为叶子结点的权值构造的哈夫曼编码树如图所示。其带权路 径长度=2X 5+1X 5+3X 4+5X 3+9X 2+4X 3+4X 3+7X 2=98，所以，该字符串的编码长度至少为98位。 2.已知关键码序列为(Ja n, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec), 散列表的地址空间为0~16,设散列函数为H(x)= ［i/2」(取下整数)，其中i为关键码 中第一个字母在字母表中的序号，采用链地址法处理冲突构造散列表，并求等概率情况下查找成功的平均查找长度。 【解答】H(Ja n)=10/2=5, H(Feb)=6/2=3, H(Mar)=13/2=6, H(Apr)=1/2=0 H(May)=13/2=6, H(Ju n)=10/25, H(Jul)=10/25, H(Aug)=1/2=0 H(Sep)=19/2=8, H(Oct) =15/2=7, H(Nov) =14/2=7, H(Dec) =4/2=2 采用链地址法处理冲突，得到的开散列表如下： 平均查找长度=(1 X 7+2X 4+3X 1)/12=18/12 3.分析下面各程序段的时间复杂度 (1)s1(int n) { int p=1,s=0; for (i=1;iv=n;i++) { p*=i;s+=p; } return(s); } ——0(n) (2)s2(int n) x=0;y=0; For (k=1;kv=n;k++) x++; For (i=1;iv=n;i++) For (j=1;jv=n;j++) y++; ——0(n) 1?下述算法的功能是什么？ ListNode *Demo l(LinkList L P ListNode *p) ("L是有头结蛊的单链表 ListNodc *q=L->rLCxt P (1) V ‘V … 」(1 )返回结点*p的直接前趋结点地址。 q=q->nest; if (q) return q, else ?ro< #*p not in L"); I ⑵ i/oid Demo2(LisINode *p ,ListNode +q) 〔//p t*q*8S 表中的 两个结点 (2)交换结点*p和结点*q (p和q的值不变)。 DataTypetemp; temp=p->data, p->data=q->data; q-x^ata^emp, 1.对给定的一组权值W=( 5, 2, 9, 11, 8, 3, 7),试构造相应的哈夫曼树，并计算它的带权路径长度。【解答】构造的哈夫曼树如图所示。 第 5 章数组和广义表 一、选择题 1.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其 存储地址为1，每个元素占一个地址空间，则a85的地址为（）。【燕山大学 2001 一、2 （2分）】 A. 13 B. 33 C. 18 D. 40 2. 有一个二维数组A[1:6，0:7] 每个数组元素用相邻的6个字节存储，存储器按字节编址， 那么这个数组的体积是（①）个字节。假设存储数组元素A[1，0]的第一个字节的地址是0， 则存储数组A的最后一个元素的第一个字节的地址是（②）。若按行存储，则A[2，4]的第 一个字节的地址是（③）。若按列存储，则A[5，7]的第一个字节的地址是（④）。就一般情 况而言，当（⑤）时，按行存储的A[I，J]地址与按列存储的A[J，I]地址相等。供选择的 答案：【上海海运学院 1998 二、2 （5分）】 ①-④： A．12 B. 66 C. 72 D. 96 E. 114 F. 120 G. 156 H. 234 I. 276 J. 282 K. 283 L. 288 ⑤： A．行与列的上界相同 B. 行与列的下界相同 C. 行与列的上、下界都相同 D. 行的元素个数与列的元素个数相同 3. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10， 数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( )。 A. BA+141 B. BA+180 C. BA+222 D. BA+225 【南京理工大学 1997 一、8 （2分）】 4. 假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存 储单元，基地址为10，则LOC[5，5]=（）。【福州大学 1998 一、10 (2分)】 A. 808 B. 818 C. 1010 D. 1020 5. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000 的内存单元中，则元素A[5，5]的地址是( )。【南京理工大学 2001 一、13 （1.5分）】 A. 1175 B. 1180 C. 1205 D. 1210 6. 有一个二维数组A[0:8,1:5],每个数组元素用相邻的4个字节存储，存储器按字节编址， 假设存储数组元素A[0,1]的第一个字节的地址是0，存储数组A的最后一个元素的第一个字 节的地址是（①）。若按行存储，则A[3,5]和 A[5,3]的第一个字节的地址是（②） 和（③）。若按列存储，则A[7,1]和A[2,4]的第一个字节的地址是（④）和（⑤）。【上海海运学院 1996 二、1 （5分）】 ①-⑤:A.28 B.44 C.76 D.92 E.108 F.116 G.132 H.176 I.184 J.188 7. 将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，A中元 素A6665（即该元素下标i=66，j=65），在B数组中的位置K为（）。供选择的答案： A. 198 B. 195 C. 197 【北京邮电大学 1998 二、5 （2分）】 8. 二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范圈 从1到10。从供选择的答案中选出应填入下列关于数组存储叙述中（）内的正确答案。（1）存放A至少需要（）个字节； （2）A的第8列和第5行共占（）个字节； （3）若A按行存放，元素A[8，5]的起始地址与A按列存放时的元素（）的起始地 2011-2012学年第一学期期末考查 《数据结构》试卷 （答案一律写在答题纸上，在本试卷上做答无效） 一、选择（每题1分，共10分） 1.长度为n的线性表采用顺序存储结构，一个在其第i个位置插入新元素的算法时间复杂度为（D） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（D） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（ B ） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（A） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（B ）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（B） A.（100,80,90,60,120,110,130） B.（100, 120, 110,130,80, 60,90） C.（100,60,80,90,120,110,130） D.（100,80, 60,90, 120, 130,110） 9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（B ） A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时，要求线性表必须（D） A.以顺序方式存储 B.以顺序方式存储，且数据元素有序 模拟试卷一 一、单选题（每题 2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点， 则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成 ( )个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。 A． 11 B.35 C. 19 D. 53 图一 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。 A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建 堆的结果?( ) 《数据结构》应用题练习 1、将下图所示的森林转换成二叉树。 2、已知一棵二叉树的中序序列和后序序列分别如下 先序序列：A B D E C F H K G 中序序列：B E D A H F K C G 请完成：（1）画出该二叉树（2分）； （2）写出该二叉树的后序序列（2分）。 3、对于一组给定的权值W=｛4,18,6,22,10,15｝,请完成： （1）建立相应的哈夫曼树； （2）计算其WPL值。 4、如下所示的有向图，回答下面问题： （1）该图是强连通的吗？若不是，给出强连通分量。 （2）请给出图的邻接矩阵 （3）请给出图的邻接表和逆邻接表。 (4) 计算各点的入度和出度 5、下图是一个带权无向图，要求： （1）画出以V1为初始顶点、按Prim算法构造最小生成树的过程； （2）求出最小生成树的总代价； （3）Prim算法求最小生成树适用于什么情形？ 6下图是一个带权无向图，要求： （1）画出以V1为初始顶点、按克鲁斯卡尔算法构造最小生成树的过程； （2）求出最小生成树的总代价； （3）克鲁斯卡尔算法求最小生成树适用于什么情形？ 7、设有一组初始记录关键字为(10, 2, 26, 4, 18, 24, 21, 15, 8,) 要求： （1）构造一棵二叉排序树并给出构造过程。 （2）查找关键字2需要和哪些结点进行比较？ （3）等概率查找下的ASL是多少？ 8、已知哈希函数为H(key)=key%11，哈希表长度为13，用平方探测再散列的方法处理冲突。 表中已依次存放了关键字为33、23、32、54和42的5个记录： （1）现将关键字65填入哈希表，确定其存储地址（要求写出每一步的哈希地址计算表达式）。 （2）若查找关键字65的记录，需依次与哪些关键字进行比较？ （3）为确保查找正确，如果删除关键字为54的记录应作何处理？ 9关键码集为{47，7，29，11，16，92，22，8，3}，散列表表长为m=11，散列函数为H(key)=key mod 11 ，线性探测法处理冲突。 （1）生成哈希表 （2）计算查找成功的ASL 课程测试试题（卷） ----------------------以下为教师填写-------------------- I、命题院（部）：数学与计算机科学学院 II、课程名称：数据结构 III、测试学期：20 －20 学年度第学期 IV、测试对象：学院专业级班 V、问卷页数（A4）：页 VI、答卷页数（A4）：页 VII、考试方式：闭卷（开卷、闭卷或课程小论文，请填写清楚） VIII、问卷内容：（请老师在出题时安排紧凑，填空题象征性的留出一点空格，学生将所有的答案做在答题纸上的规定位置，并写清楚大题、小题的题号） 一、单选题（每题 2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指 向的结点，则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多 可以组成( )个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为 ( )。 以下6-8题基于图1。 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B.E、A、G、C、F、B、D C.E、A、C、B、D、G、F D.E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F E.B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。 A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述 序列出发建堆的结果?( ) A. a，g，h，m，n，p，q，x，z B. a，g，m，h，q，n，p，x，z C. g，m，q，a，n，p，x，h，z D. h，g，m，p，a，n，q，x，z 二、填空题（每空1分，共26分） 1.数据的物理结构被分为_________、________、__________和___________四 种。 2.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为 _________，在表尾插入元素的时间复杂度为____________。 3.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是 ________________;删除一个结点时，需要执行的操作是 ______________________________（假设栈不空而且无需回收被删除结点）。 第10章排序 一、选择题 1．某内排序方法的稳定性是指( )。【南京理工大学 1997 一、10（2分）】A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录 C．平均时间为0（n log n）的排序方法 D．以上都不对 2．下面给出的四种排序法中( )排序法是不稳定性排序法。【北京航空航天大学 1999 一、 10 （2分）】 A. 插入 B. 冒泡 C. 二路归并 D. 堆积 3．下列排序算法中，其中（）是稳定的。【福州大学 1998 一、3 (2分)】 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序 4．稳定的排序方法是（）【北方交通大学 2000 二、3（2分）】 A．直接插入排序和快速排序 B．折半插入排序和起泡排序 C．简单选择排序和四路归并排序 D．树形选择排序和shell排序 5．下列排序方法中，哪一个是稳定的排序方法？（）【北方交通大学 2001 一、8（2分）】 A．直接选择排序 B．二分法插入排序 C．希尔排序 D．快速排序6．若要求尽可能快地对序列进行稳定的排序，则应选（A．快速排序 B．归并排序 C．冒泡排序）。 【北京邮电大学 2001 一、5（2分）】 7．如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。（）就是不稳定的排序方法。【清华大学 1998 一、3 (2分）】 A．起泡排序 B．归并排序 C．Shell排序 D．直接插入排序 E．简单选择排序 8．若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（）排序为宜。 A．直接插入 B．直接选择 C．堆 D．快速 E．基数【中科院计算所 2000 一、5（2分）】 9．若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。 A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序【中国科技大学 1998 二、4（2分）】【中科院计算所 1998 二、4（2分）】 10．下面的排序算法中，不稳定的是（）【北京工业大学 1999 一、2 (2分)】 A.起泡排序 B.折半插入排序 C.简单选择排序 D.希尔排序 E.基数排序 F.堆排序。 11．下列内部排序算法中：【北京工业大学 2000 一、1 (10分每问2分)】A．快速排序 B.直接插入排序 C. 二路归并排序 D. 简单选择排序 E. 起泡排序F. 堆排序 （1）其比较次数与序列初态无关的算法是（）（2）不稳定的排序算法是（）（3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k< 一、选择题。(每小题2分，共40分) (1) 计算机识别.存储和加工处理的对象被统称为____A____。 A.数据 B.数据元素 C.数据结构 D.数据类型 (2) 数据结构通常是研究数据的____ A _____及它们之间的联系。 A.存储和逻辑结构 B.存储和抽象 C.理想和抽象 D.理想与逻辑 (3) 不是数据的逻辑结构是____ A ______。 A.散列结构 B.线性结构 C.树结构 D.图结构 (4) 数据结构被形式地定义为数据结构复习题附答案
数据结构题库教材
目前最完整的数据结构1800题包括完整答案 第五章 数组和广义表
《数据结构》期末考试题及答案
《数据结构》模拟试卷一及答案
《数据结构》应用题练习
数据结构期末模拟试题05(有答案)
目前最完整的数据结构1800题包括完整答案 第十章 排序
数据结构复习题及答案(12级).
- C语言 数据结构典型例题
- 数据结构典型例题
- 数据结构应用题答案
- 湖南科技大学数据结构综合应用题
- 数据结构应用题
- 历年数据结构-应用题汇总
- 数据结构题库-应用题(上海杉达学院期末总复习题)
- 数据结构计算题及参考答案
- 第9章 综合应用题数据结构
- 数据结构应用题整理
- 数据结构应用题
- 关于数据结构栈的应用题
- 2024王导数据结构综合应用题
- 数据结构自学考试辅导--应用题
- 数据结构应用题练习
- 《数据结构》大题及答案
- 数据结构附部分答案
- 《数据结构》应用题参考习题
- 2021年东华大学计算机科学与技术学院854计算机及软件工程专业基础综合考研核心题库之数据结构应用题
- 数据结构题库应用题上海杉达学院期末总复习题