作业题（一）
一、单项选择题
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))的结果是（）。
A．BCDEF B．BCDEFG
C．BCPQRST D．BCDEFEF
10、数组常用的两种基本操作是（）。
A．建立与查找 B．删除与查找
C．插入与索引 D．查找与修改
二、填空题
1. 所谓稀疏矩阵指的是________且分布没有规律。
2. 队列是________的线性表，其运算遵循________的原则。
3. 空格串是________________________________。
4.简单选择排序和起泡排序中比较次数与序列初态无关的算法有________。
5、设图G有n个顶点和e条边，则对用邻接矩阵表示的图进行深度或广度优先搜索遍历时的时间复杂度为，而对用邻接表表示的图进行深度或广度优先搜索遍历时的时间复杂度为，图的深度或广度优先搜索遍历时的空间复杂度均为。
6、一个图的表示法是唯一的，而表示法是不唯一的。
三、算法
设二叉树采用二叉链表结构，试设计一个算法统计给定二叉树中的一度结点数目。
四、应用题
1、对关键字无序序列(36，25，48，12，65，43，20，58)进行直接选择排序，请写出每一趟排序的结果。（10分）
2、对无向带权图，用克鲁斯卡尔算法构造最小生成树。（10分）
3、已知记录关键字集合为（53,17,19,61,98,75,79,63,46,49）要求散列到地址区间（100,101,102,103,104,105,106,107,108,109）内，若产生冲突用开型寻址法的线性探测法解决。要求写出选用的散列函数；形成的散列表；计算出查找成功时平均查找长度与查找不成功的平均查找长度。（设等概率情况）
4、设被查找文件有4095个记录，对每个记录查找记录概率相等，若采用顺序查找，成功查找平均比较次数为多少？
作业题（二）
、单项选择题
1. 有六个元素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
2. 栈和队都是（）
A．顺序存储的线性结构 B. 链式存储的非线性结构
C. 限制存取点的线性结构
D. 限制存取点的非线性结构
3、顺序查找法适合于存储结构为（）的线形表。
A．散列存储B．顺序存储或链接存储
C．压缩存储D．索引存储
4、分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( )。
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)
5、折半查找的平均比较次数为（）。
A．n B．n/2
C．log2n D．log2(n+1)
6、当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度（）
A．必定快B．不一定
C．在大部分情况下要快D．取决于表递增还是递减
7、已知一有向图的邻接表存储结构如下图如示。根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是（）。
A．v1，v2，v3，v5，v4 B．v1，v2，v3，v4，v5
C．v1，v3，v4，v5，v2 D．v1，v4，v3，v5，v2
8、为了方便地对图状结构的数据进行存取操作，则其中数据存储结构宜采用（）。
A．顺序存储B．链式存储
C．索引存储D．散列存储
9、在一个具有n个顶点的有向图中，若所有顶点的出度之和为s，则所有顶点的入度之和为（）。
A．s B．s-1
C．s+1 D．n
10、如图所示，给出由7个顶点组成的无向图。从顶点A出发，对它进行深度优先搜索得到的顶点序列是（）。
A．A E C D B F G B．A G B F D E C
C．A C E D B G F D．A B D G F E C
二、填空题
1. 设n0为哈夫曼树的叶子结点数目，则该哈夫曼树共有________个结点。
2. 有数据WG={7，19，2，6，32，3，21，10}，则所建Huffman树的树高是________，带权路径长度WPL 为________。
3.设一棵完全二叉树叶子结点数为k,最后一层结点数>2，则该二叉树的高度为________________。
4.采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分个结点最佳。
5、设G为具有N个顶点的无向连通图，则G中至少有条边。
6、哈夫曼树（Huffman Tree）又称。它是n个带权叶子结点构成的所有二叉树中，带权路径长度WPL 。
7、树的先序遍历过程如下：若树为空，则进行空操作；若树非空，则访问树的；依次先序遍历树的。
三、应用题
1、给定权值集合{1, 4, 2, 6, 9,}, 构造相应的哈夫曼树, 并计算它的带权路径长度。
2、对关键字序列{10，6，3，2，5，4}，构造一棵平衡二叉（排序）树并画图（要求画出建树过程）。
3、设有一个有序文件，其中各记录的关键字为（1，2，3，4，5，6，7，8，9，10，11，12，13，14，15），当用折半查找算法查找关键字为3，8，19时，其比较次数分别为多少？
4、对有五个结点{ A,B, C, D, E}的图的邻接矩阵， ????????????????∞∞∞∞∞∞∞∞∞∞∞∞∞05001020060010301000 （1）．画出逻辑图 ；
（2）．画出图的十字链表存储；
（3）．基于邻接矩阵写出图的深度、广度优先遍历序列； （4）．计算图的关键路径。
作业题（三）
一、单项选择题 1．串的长度是指（ ）
A ．串中所含不同字母的个数
B ．串中所含非空格字符的个数
C ．串中所含不同字符的个数
D ．串中所含字符的个数
2．设有数组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 3．算法分析的两个主要方面是（ ）。
A ．空间复杂性和时间复杂性
B ．正确性和简明性
C ．可读性和文档性
D ．数据复杂性和程序复杂性 4．算法分析的目的是（ ）。
A．找出数据结构的合理性 B．研究算法中的输入和输出的关系
C．分析算法的效率以求改进 D．分析算法的易懂性和文档性
5.下面程序段的时间复杂性的量极为（）。
Int fun(int n)
{ int i=1,s=1;
While(s S+= ++I; Return I; } A．O(n/2) B．O(lbn) C．O(n) D．O( ) 6.线性表是（）。 A．一个有限序列，可以为空 B．一个有限序列，不能为空 C．一个无限序列，可以为空 D．一个无限序列，不能为空 7.带头结点的单链表L为空的判定条件是（）。 A．L= =NULL B．L-〉next= =NULL C．L-〉next= =L D．L! =NULL 8.在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为（）。 A．（n+1）/2 B．n/2 C．n D．n+1 9.一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是（）。 A．98 B．100 C．102 D．106 10.如果某链表中最常用的操作是取第i个结点及其前驱，则采用（）存储方式最节省时间。 A．单链表 B．双向链表 C．单循环链表 D．顺序表 二、填空题 1. 高度为2的二叉树的结点数至少有________个，高度为3的二叉树的结点数至少有________个。 2. 在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用折半查找关键字值20，需做的关键字比较次数为________。 3.在有n个顶点的无向图中，每个顶点的度最大可达________。 4．已知广义表A=（（a，b，c），（d，e，f）），则广义表运算head（tail（tail（A）））= 。 5、数组（Array）是n（n≥1）个的有序组合，数组中的数据是按顺序存储在一块的存储单元中。 6.采用顺序存储结构表示三元组表（Triple Table），来实现对稀疏矩阵的一种压缩存储形式，就称为，简称表。 7. 运算是矩阵运算中最基本的一项，它是将一个m x n的矩阵变成另外一个n x m的矩阵，同时 使原来矩阵中元素的行和列的位置互换而值保持不变。 三、应用题 1、对于下图所示的二叉树，画出二叉链表存储结构图。 2、请画出下图所示的树所对应的二叉树。 3.已知一个无向图如下图所示，要求分别用Prim和Kruskal算法生成最小树（假设以①为起点，试画出构造过程）。 4.已知完全二叉树的第8层有8个结点，则其叶子结点是多少？ 5. 画出如图所示中树的二叉树的表示形式。 A B C D E 作业题（四） 一、单项选择题 1. 将两个各有n个元素的有序表归并成一个有序表，其最少得比较次数是（）。 A．n B．2n-1 C．2n D．n-1 2. 一个有n个顶点的无向连通图，它所包含的连通分量个数为（）。 A．0 B．1 C．n D．n+1 3. 数据文件的基本操作中最重要的操作是（）。 A．插入B．删除 C．修改D．检索 4. 对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（）。A．(2,5,12,16)26(60,32,72) B．(5,16,2,12)28(60,32,72) C．(2,16,12,5)28(60,32,72) D．(5,16,2,12)28(32,60,72) 5. 如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（）方法最快。A．堆排序B．快速排序 C．插入排序D．归并排序 6．算法分析的目的是（）。 A．找出数据结构的合理性 B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进 D．分析算法的易懂性和文档性 7. 二叉树的第I层上最多含有结点数为（） A．2I B． 2I-1-1 C． 2I-1 D．2I -1 8．循环队列存储在数组A中，长度为m，则入队时的操作为（）。 A. rear=rear+1 B. rear=(rear+1) mod (m-1) C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1) 9. 广义表满足Head(A)=Tail(A)，则A为（）。 A．（）B．（（）） C．（（），（））D．（（），（），（）） 10. 在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（）个。 A．3 B．4 C．5 D．6 二、填空题 1. 在一个循环队列中，队首指针指向队首元素的_________。 2. 数组中每一个数据通常称为，用下标区分，其中下标的个数由数组的决定。 3. 一个图的表示法是唯一的，而表示法是不唯一的。 4. 在一个10阶的B-树上，每个数根结点中所含的关键字数目最多允许 个，最少允许个 5. 对关键字序列（52，80，63，44，48，91）进行一趟快速排序之后的得到结果为。 10.高度为1的平衡二叉树的结点数至少有________个，高度为2的平衡二叉树的结点数至少有________个。 三判断 1. 顺序存储结构属于静态结构，链式结构属于动态结构。（） 2. 即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列也一定相同。（） 3. 带权无向图的最小生成树必是唯一的。（） 4. B-树和B+树都可用于文件的索引结构。（） 5. 在用堆排序算法排序时，如果要进行增序排序，则需要采用"大根堆"。（） 四、应用题 1. 模式串p="abaabcac"的next函数值序列为多少？ 2. 设二维数组A[5][6]的每个元素占4个字节，已知LOC（a0,0）=1000，A共占多少个字节？A的终端结点a4,5的起始地址为多少？按行和按列优先存储时，a2,5的起始地址分别为多少？ 3. 设a,b,c,d,e五个字符的编码分别为1,2,3,4,5，并设标识符依以下次序出现：ac,bd,aa,be,ab,ad,cd,bc,ae,ce。要求用哈希（Hash）方法将它们存入具有10个位置的表中。 （1）将上述关键字（标识符）构造一个哈希函数，使得发生冲突尽可能地少；（2）线性探测再散列法解决冲突。写出上述各关键字在表中位置。 4. 给定一个关键字序列{24，19，32，43，38，6，13，22}，请写出快速排序第一趟的结果；堆排序时所建的初始堆；归并排序的全过程。然后回答上述三中排序方法中那一种方法使用的辅助空间最少？在最坏情况下那种方法的时间复杂度最差？ 作业题（五） 一、单项选择题 1. 一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。 A．(38,40,46,56,79,84) B．(40,38,46,79,56,84) C．（40,38,46,56,79,84) D．(40,38,46,84,56,79) 2．广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（）。GetHead(GetTail(GetHead(GetTail(GetTail(A))))) A. (g) B. (d) C. c D. d 3．对于有n 个结点的二叉树, 其高度为（） A．nlog2n B．log2n C．?log2n?+1 D．不确定 4. 如图所示，给出由7个顶点组成的无向图。从顶点1出发，对它进行深度优先搜索得到的顶点序列是（）。 A．1 3 5 4 2 6 7 B．1 3 4 7 6 2 5 C．1 5 3 4 2 7 6 D．1 2 4 7 6 5 3 5. 采用邻接表存储的图，其深度优先遍历类似于二叉树的（）。 A．中序遍历B．先序遍历 C．后序遍历D．按层次遍历 6. 已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={ A．V1,V3,V4,V6,V2,V5,V7B．V1,V3,V2,V6,V4,V5,V7 C．V1,V3,V4,V5,V2,V6,V7D．V1,V2,V5,V3,V4,V6,V7 7. 顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为（）。在此假定N为线性表中结点数，且每次查找都是成功的。 A．N+1 B．2log2N C．log2N D．N 8. 下面关于m阶B树说法正确的是（）。 ①每个结点至少有两棵非空子树；②树中每个结点至多有m一1个关键字； ③所有叶子在同一层上；④当插入一个数据项引起B树结点分裂后，树长高一层。 A．①②③B．②③ C．②③④D．③ 9. 已知一个线性表（38，25，74，63，52，48），假定采用h(k)=k%7计算Hash地址进行散列存储，若利用链地址法处理冲突，则在该Hash表上进行查找的平均查找长度为（）。 A．1.0 B．7/6 C．4/3 D．3/2 10. 在排序算法的实施过程中，使用辅助存储空间为O（1）的有（）。 A．简单排序法B.快速排序法 C．归并排序法D.基数排序法 二、填空题 1. n（n大于1）个结点的各棵树中，其中深度最大的那棵树的深度是n，它共有________个叶子结点和________个非叶子结点。 2.设一棵后序线索树的高是50，结点x是树中的一个结点，其双亲是结点y,y的右子树高度是60，x是y 的左孩子。则确定x的后继最多需经过________中间结点（不含后继及x本身） 3.高度为2（第2层为叶子）的3阶B-树中，最多有________个关键字。 4.分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为无序的表，则平均情况下最省时间的是________算法。 5.简单选择排序和起泡排序中比较次数与序列初态无关的算法有________。 6. 串的链式存储结构是将存储区域分成一系列大小相同的结点,每个结点有两个域域和域。其中域用于用于存放数据，域用于存放下一个结点的指针 三．判断 1. 顺序存储的线性表可以随机存取。（） 2. 即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列也一定相同。（） 3. 十字链表是无向图的一种存储结构。（） 4. 折半查找方法适用于排列连续顺序文件的查找。（） 5. 在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（） 四、应用题 1. 用十字链表表示一个有k个非零元素的m x n的稀疏矩阵，则其总的结点数为多少？ 2. G=(V,E)是一个带有权的连通图,则： （1）．请回答什么是G的最小生成树； （2）．G为下图所示,请找出G的所有最小生成树。 3. 请分别叙述在一个连续顺序文件中采用顺序查找法，折半查找法和分块查找法查找一个记录，该文件中记录应该满足什么条件？ 4. 设待排序文件之排序码为（88，33，22，55，99，11，66），采用顺序存储。请用直接选择排序算法对上述文件进行排序，用图示说明排序过程。 ---------------------------------------------- 作业题一参考答案： 一、单项选择题 1、C 2、B 3、D 4、C 5、B 6、B 7、A 8、C 9、D 10、D 二、填空题 1、非零元很少 2、操作受限（或限定仅在表尾进行插入和限定仅在表头进行删除操作或限制存取点或特殊），先进先出(或后进后出) 3、简单选择排序 4、O(n2)，O(e)，O(n) 5、邻阵矩阵，邻接表 三、算法 答： int count = 0; void onechild ( Btree t) { if ( t!=NULL) { onechild ( t->lchild ); onechild ( t->rchild ); if ( t->lchild!=NULL && (t->rchild!=NULL || t->lchild!=NULL && t->rchild==NULL ) count++; } } 四、应用题 1、 答： 2、 答： （1） （2） （3） （4） 1 G C 3 A 3 A 1 C 2 F G （5）（6） 3、答：由于地址空间为10，且从100开始，故散列函数选为H（key）=key%7+100。 用线性探测再散列解决冲突，ASLsucc=27/10 4、答：成功查找平均比较查找长度为：（n+1）/n[log2（n+1）]-1。 作业题二参考答案： 一、单项选择题 1、C 2、C 3、B 4、C 5、D 6、C 7、C 8、B 9、A 10、C 二、填空题 1、2n0-1 2、6，261 3、?log2k?+1 4、25 5、N-1 6、最优二叉树，最小的二叉树 7、根结点，各子树 三、应用题 2 F G 4 2 F G 3 A D 4 B 5 E 6 1 C 2 F G 1 C 1 C 2 F G 3 A D 4 B 5 1 C 1、 答：不唯一，型对即可 此树的带权路径长度WPL =9*1+6*2+4*3+(1+2)*4=45 2、 答： （1）插入10 (2) 插入6 (3) 插入3 (4) （ 5）插入2 （6 ）插入5 （7 ）插入4 （8） 3、答：当关键字为3时，比较次数为4；当关键字为8时，比较次数为1； 当关键字为19时，查找不成功； 4、答：（2）略 （3）深度优先遍历序列：ABCDE 广度优先遍历序列：ABCED （4）关键路径A--B （长100） 作业题三参考答案： 一、单项选择题 1、D 2、B 3、A 4、C 5、D 6、A 7、B 8、C 9、B 10、D 二、填空题 1、2，3 2、4 3、n-1 4、e 5、相同类型数据，地址连续 6.三元组顺序表，三元组 7. 矩阵转置 三、应用题 1、 答： 二叉链表 (2 2、答： 3. 答：Prim 算法构造最小生成树的步骤如24题所示，为节省篇幅，这里仅用Kruskal 算法，构造最小生成树过程如下：（下图也可选(2,4)代替(3,4),(5,6)代替(1,5)） B C D E A ① ② ③ ④ ⑤ ⑥ ⑦ ⑨ ⑧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ 即： 4. 答：由完全二叉树的定义可知，除最后一层外，其他各层的结点是满的。设该完全二叉树有d层，则除最后一层外各层的结点个数分别为：1，2，4，8，16，32，…，即第i层的结点个数为2i-1。这里第8层有8个结点，显然第8/层是最后的一层，那么第7层的结点个数为27-1=64个，其中的4个结点有8个叶子结点，余下的为叶子结点，个数为64-4=60，所以该完全二叉树的叶子结点个数为60+8=68个。 5. 答：对应的二叉树形式如图所示： 作业题四参考答案： 一、单项选择题 1. A 2. B 3. D 4. B 5. D 6、C 7、C 8、C 9、B 10、D 二、填空题 1. 答：前一个位置 2. 答：数组元素，数组元素，维数 3. 答：邻阵矩阵，邻接表 4. 答：9，4 5. 答：[48 44] 52 [64 80 91] 6、1，2 三．判断 1. 答：√ 2. 答：× 3. 答：× 4. 答：√ 5. 答：√ 四、应用题 1. 答：模式p的next函数值如下： 2. 答：A共120个字节。 a4,5的起始地址为：1116。 按行优先存储时，a2,5的起始地址为：1068。 按列优先存储时，a2,5的起始地址为：1108。 3. 答：（1）哈希函数H（key）=（关键字各字符编码之和）MOD 7（2） 4. 答：一趟快速排序：22,19,13,6,24,38,43,32 初始大堆：43,38,32,22,24,6,13,19 二路并归：第一趟：19,24,32,43,6,38,13,22 第二趟：19,24,32,43,6,13,22,38 第三趟：6,13,19,22,24,32,38,43 堆排序辅助空间最少，最坏情况下快速排序时间复杂度最差。 作业题五参考答案： 一、单项选择题 1. 答：C 2、D 3、D 4. 答：C 5. 答：B 6. 答：A 7. 答：D 8. 答：B 9. 答：C 10. 答：A 二、填空题 1、1，n-1 2、60 3、2 4、快速排序 5、简单选择排序 6．数据，指针，数据，指针 三判断 1. 答：√ 2. 答：× 3. 答：× 4. 答：√ 5. 答：× 四、应用题 1. 答：该十字链表有一个十字链表表头结点，max(m,n)个行列表头结点。另外，每个非零元素对应一个结点，即k个元素结点，所以共有max(m,n)+k+1个结点。 2. 答：（1）最小生成树的定义略。（2）最小生成树有两棵。（限于篇幅，下面的生成树只给出顶点集合和边集合，边以三元组（Vi,Vj,W）形式），其中W代表权值。V（G）={1，2，3，4，5} E1(G)={(4，5， 2)，（2，5，4），（2，3，5），（1，2，7）}；E2(G)={(4，5，2），（2，4，4），（2，3，5），（1，2，7）} 3. 答：采用顺序查找法：文件中记录可以以任意持续存放。 采用折半查找法：文件中的记录必须按照关键字从小到大有序存放。 采用分块查找法：将文件分成若干个块，每一个快中的记录可以任意的存放，但块之间的必须按照关键字 从小到大的次序存放，即前一块中的所有记录的关键字的值必须小于后一块的所有记录的关键字的字值。 4. 答：排序过程如下： (1)[]88,33,22,55,99,11,66 (2)[11],33,22,55,99,88,66 (3)[11,22],33,55,99,88,66 (4)[11,22,33],55,99,88,66 (5)[11,22,33,55],99,88,66 (6)[11,22,33,55,66],99,88 (7)[11,22,33,55,66,88],99 (8)[11,22,33,55,66,88,99] 、单项选择题 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)) 的结果是( )。 作业题(一) 1. 从逻辑上可以把数据结构分为( A.动态结构、静态结构 B C.线性结构、非线性结构 D 2. 链表不具有的特点是( ) A 插入、删除不需要移动元素 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 C . O(n2) D 4. 在一个带头结点的双向循环链表 中， 个指针域的值。 )两大类。 .顺序结构、链式结构 .初等结构、构造型结构 B .可随机访问任一元素 所 需空间与线性长度成正比 )。 . O(n) . O(n3) 若要在 p 所指向的结点之前插入一个新结点， 则需要相继修改 ( ) (A )数据的逻辑结构 (B )数据的存储结构 《数据结构》专升本考试试题 (2015 年 3 月) (C )数据的逻辑结构和存储结构 12.算法分析的两个主要方面是( (A )空间复杂度和时间复杂度 (C )可读性和文档性 (D )数据的逻辑结构、存储结构及其基本操作 )o (B )正确性和简单性 (D )数据复杂性和程序复杂性 一、单项选择题(本大题共 20小题，每小题2分，共40分) 1 ?对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为( (A) 正确性 (B) 可行性 ( C) 健壮性 2 ?设S 为C 语言的语句,计算机执行下面算法时， for(i=n-1 ； i>=0 ； i--) for(j=0 ; jn ext==head (B ) p-> next==NULL (C ) p==NULL (D ) p==head 16. 一个栈的输入序列为： a ，b ，c ，d ，e ，则栈的不可能输出的序列是( )o (A ) a,b,c,d,e (B ) d,e,c,b,a (C ) d,c,e,a,b (D ) e,d,c,b,a 17.设SUBSTR(S,i,k)是求S 中从第i 个字符开始的连续k 个字符组成的子串的操作，则对 5 ?深度为k 的完全二叉树，其叶子结点必在第( (A ) k-1 (B ) k (C ) k-1 和 k (D ) 6?具有60个结点的二叉树，其叶子结点有12个， (A ) 11 ( B ) 13 (C ) 48 ( D 37 利于删除操作 利于随机访问 )层上。 1至k 则度为1的结点数为( 7.图的Depth-First Search(DFS) 遍历思想实际上是二叉树( (A )先序 (B )中序 (C )后序 (D )层序 8 .在下列链队列Q 中，元素a 出队的操作序列为( )遍历方法的推广。 S= ' Beijing&Nanjing '，SUBSTR(S,4,5)=( ) (A )‘iji ng ' (B )' jing& ' (C )' ingNa ' (D ) 'ing&N ' 18.广义表((a),a) 的表尾是( )o (A ) a (B ) (a) (C )() (D ) ((a)) 19. 在一棵具有5层的满二叉树中结点总数为( )o (A ) 31 (B ) 32 (C ) 33 (D ) 16 20. 如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是( )o (A )完全图 (B )连通图 (C )有回路 (D ) —棵树 二、填空题(本大题共20个空，每空2分，共40分) Q (A ) (B ) (C ) (D ) p=Q.fr ont->n ext; p->n ext= Q.front->n ext; p=Q.fr ont->n ext; Q.front->n ext=p->n ext; p=Q.rear- >n ext; p->n ext= Q.rear- >n ext; p=Q->n ext; Q->n ext=p->n ext; 1 .逻辑结构决定了算法的 ____________ ，而存储结构决定了算法的 _____________ o 2. _______________________ 栈和队列都是一种 ______________________ 的线性表，栈 和删除只能在 ______________ 进行。 3. 线性表(a 1,a 2,…,a n )的顺序存储结构中，设每个单元的长度为L,元素a i 的存储地址LOC 4. 已知一双向链表如下(指针域名为next 和prior): 9. Huffman 树的带权路径长度WP 等于( (A )除根结点之外的所有结点权值之和 (C )各叶子结点的带权路径长度之和 )域存储后继结点的地址。 (C ) rchild (D ) root )o 10?线索二叉链表是利用( (A ) Ichild (B ) data 11 ?研究数据结构就是研究( (B ) (D ) ) 所有结点权值之和 根结点的值 现将p 所指的结点插入到x 和y 结点之间，其操作步骤为： ________________________ 5 . n 个结点无向完全图的的边数为 ________________________ ， n 个结点的生成树的边 为 ____________________ o 数据结构试题及答案 一、单项选择题 (1)一个算法应该就是（)。 A)程序???B）问题求解步骤得描述 C）要满足五个基本属性??D) A与C (2)算法指得就是（)。 A）计算机程序???B）解决问题得计算方法 C)排序算法???D）解决问题得有限运算序列。 (3)与数据元素本身得形式、内容、相对位置、个数无关得就是数据得(）。 A) 存储结构B) 逻辑结构C）算法D)操作 (4)从逻辑上可以把数据结构分为( ）两大类。 A）动态结构、静态结构??B) 顺序结构、链式结构 C）线性结构、非线性结构???D）初等结构、构造型结构 (5)下列叙述中正确得就是(）。 A)一个逻辑数据结构只能有一种存储结构 B）数据得逻辑结构属于线性结构,存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理得效率 D）一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理得效率 (6)数据得基本单位就是（） ?A) 数据项??B) 数据类型C)数据元素??D)数据变量 (7)下列程序得时间复杂度为（) i=０；s＝０; wｈｉlｅ(s 《数据结构》模拟题（补） 一．单项选择题 1.在线性表的下列存储结构中，读取元素花费时间最少的是【】。 A．单链表B．双链表C．顺序表D．循环链表 2.设计一个判定表达式中左、右括号是否配对出现的算法，采用【】数据结构最佳。 A．集合B．线性表C．队列D．栈 3.n个结点的线索二叉树上含有的线索数为【】。 A．2n B．n-1 C．n D．n+1 4.设广义表D=(a,(b,c)),则tail(D）=【】。 A．b,c B．(b,c) C．((b,c)) D．c 5.由4个结点可以构造出【】种不同的二叉树。 A．12 B．13 C．14 D．15 6.在栈中，出栈操作的时间复杂度为【】。 A．O(1) B．O(n) C．O(log2n) D．O(n2) 7.假设Q[0..len-1]表示循环队列，f为队头指针，r为队尾指针，则进队操作语句是【】。 A．f=f+1 B．r=r+1 C．f=(f+1)%len D．r=(r+1)%len 8.一个n*n的对称矩阵，如果以行或列为主序放入内存，则其容量为【】。 A．n*n B．n*n/2 C．n*(n+1)/2 D．(n+1)*(n+1)/2 9.队列操作的原则是【】。 A．进优于出B．出优于进C．先进先出D．后进先出 10.下列数据结构中，【】是非线性数据结构。 A．栈B．串C．队列D．树 11.两个指针p和q，分别指向单链表的两个元素，p所指元素是q所指元素的前驱，则【】。 A．p==q B．q->next=p C．p->next=q D．p->next=q->next 12.数组A中，每个元素的长度为4个字节，行下标i从1到5，列下标j从1到4，从首 地址SA开始连续存放在存储器内，该数组按行存放时，元素A[3][2]的起始地址为【】。 A．SA+20 B．SA+36 C．SA+40 D．SA+45 13.已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为d1， 则第i个结点的地址为【】。 A．d1+(i-1)*m B．d1+i*m C．d1+(i+1)m D．d1-i*m 14.分析下列算法suanfa1(n)的时间复杂度是【】。 void suanfa1(int n) { int i,j,x=1； for(i=0；i 《数据结构》教学大纲 课程性质专业必修课 课程名称数据结构课程编号*04069 适用专业计算机科学与技术/软件工程开课学期第3学期 总学时64 理论50 学分数 4 实践14 一、课程性质与目标 数据结构课程属于专业必修课。通过本课程数据结构的学习，学生应实现如下目标： 1.知识目标：本课程主要讲述线性表、栈、队列、字符串、数组、树、二叉树、图、查找表、内部排序等常用数据结构的基本概念、操作及其典型应用例子。通过本课程的学习，应使学生掌握数据结构的概念及不同的存储结构、掌握一些典型算法原理和方法，且能够在不同存储结构上实现编程，同时，对于算法设计的方式和技巧也有所体会。 2.能力目标 （1）独立获取知识的能力——逐步掌握科学的学习方法，不断地扩展知识面，增强独立思考的能力，更新知识结构； （2）科学观察和思维的能力——运用数据结构的基本理论，熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构。 （3）分析问题和解决问题的能力——学会利用数据结构原理分析实际问题，提高发现问题与解决问题的能力。对部分优秀的学生，培养其在知名程序设计在线评测系统（如POJ等）中求解实际问题的能力。 （4）求实精神——通过数据结构理论课程教学，培养学生严谨求实的科学态度和刻苦钻研的作风。 （5）实践能力——通过学习，有意识地培养学生编写高质量、高效率程序的能力和风格。 3.素质目标：使学生具备一定的计算思维，热爱算法设计和程序实现，面对实际问题能转换为计算机能够求解的过程并选择合适的数据结构，设计出在时间和空间上具备一定高效率的程序，培养学生学习算法设计与实现的细心和耐心，培养学生坚韧不拔，攀登技术高峰的优秀品质。让部分优秀的学生热爱上湖南省大学生程序设计竞赛，体会ACM程序设计竞赛的魅力。 二、课程教学基本要求 课程前应该认真预习，特别是前导课程相关知识体系; 课中应该认真听课，参与教学过程中的互动、回答问题及联系实际编程; 课后积极做好复习、认真完成作业及课程设计相关实践教学的环节。作业应具备一定实用性的数据结构和算法实现为主，对部分优秀学生，引入一定量的知名程序设计在线评测系统（如POJ等）中与数据结构相关的题目进行编程并在线提交验证正确性与时间、空间效率。 三、教学内容与学时分配 山东:07年专升本考试数据结构模拟试题1 一、填空题:(每小题2分,共10分 1. 设有数据结构(D,R,其中 D 是数据元素的有限集,R 是的有限集。 2. 深度为 k 的二叉树其结点数至多有个。 3. 栈是一种特殊的线性表,它允许在表的一端进行操作。 4. 通常象交通、道路问题的数学模型是一种称为的数据结构。 5. 哈希表是一种查找表,可以根据哈希函数直接获得。 二、单项选择题:(每小题2分,共10分 对于下列各题,在备选答案中选出一个正确的,并将其编号填在“”位置上。 1. 若线性表最常用的操作是存取第 i 个元素及其前驱元素的值,则采用存储方式最节省运算时间。 A. 单链表 B. 双链表 C. 单循环链表 D. 顺序表 2. 下列排序算法中,算法在进行一趟相应的排序处理结束后不一定能选出一个元素放到其最终位置上。。 A. 直选择排序 B. 冒泡排序 C. 归并排序 D. 堆排序 3. 队列的操作原则是。 A. 先进后出 B. 先进先出 C. 只能进行插入 D. 只能进行删除 4. 在具有 n 个结点的二叉链表中,非空的链域个数为。 A. n-1 B. n C. n+1 D. 不确定 5. 对具有 n 个元素的有序查找表采用折半查找算法查找一个键值,其最坏比较次数的数量级为。 A. O(log2n B. O(n C. O(nlog2n D. O(n2 三、判断题:(每小题2分,共10分 判断下列各题是否正确,若正确,在题后的括号内填“T”,否则填“F”。 1. 在栈为空的情况下不能作出栈处理,否则,将产生下溢出。( 2. 如果有向图 G=(V, E 的拓扑序列唯一,则图中必定仅有一个顶点的入度为0、一个顶点的出度为0。( 3. 在大根堆中,必定满足每个结点的键值大于其左右子树中所有结点的键值。( 4. 在采用线性探测法处理冲突的散列表中所有同义词在表中相邻。( 5. 在索引顺序表中,对索引表既可采用顺序查找,也可采用二分查找。( 四、解答下列各题:(每题10分,共40分 1. 已知线性表 L 采用带头结点的的单向循环链表表示,试给出它的存储结构类型描述及相应的示意图。。 2. 已知一棵二叉树的先序、中序和后序序列如下所示,请填写各序列中空格处的结点,并画出该二叉树的二叉链表存储结构示意图。 先序序列是:_ B _ F _ I C E H _ G;中序序列是:D _ K F I A _ E J C _ ; 后序序列是:_ K _ F B H J _ G _ A 3. 已知数据表为(48,70,33,65,24,56,12,92,86,22,a 写出采用快速排序算法进行排序时第一趟快速划分的详细过程及结果;b 写出按基数排序思想对最低位进行一次分配和收集的结果。 4. 对图1所示的带权无向图,写出它的邻接矩阵和深度优先搜索序列,并按克鲁斯卡算法求其最小生成树(写出求解的详细过程示意图。 图1 带权无向图 五、算法设计题:(前两题必做,每题15分,共30分;第三题为附加题,选做,10分 《数据结构》题库及答案 一、选择题 1．线性表的顺序存储结构是一种 的存储结构，线性表的链式存储结构是一种 的存储结构。 a. 随机存储； b.顺序存储； c. 索引存取； d. HASH 存取 2．一个栈的入栈序列是a,b,c,d,e ，则栈的不可能的输出序列是 。 a. edcba; b. decba; c. dceab; d.abcde 3．一个队列的入队序列是1，2，3，4，则队列的输出序列是 。 a. 4,3,2,1; b. 1,2,3,4; c. 1,4,3,2; d.3,2,4,1 4．在一个单链表中，已知p 结点是q 结点的直接前驱结点，若在p 和q 之间插入结点s ，则执行的操作是 。 a. s->nxet=p->next; p->next=s; b. p->next=s->next; s->next=p; c. q->next=s; s->next=p; d. p->next=s; s->next=q; 5．设有两个串p,q ，求q 在p 中首次出现的位置的运算称作 。 a.联接 b.模式匹配 c.求子串 d.求串长 6．二维数组M 的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i 的范围从0到8，列下标j 的范围从1到10，则存放M 至少需要 个字节。 a. 90 b.180 c.240 d.540 7．在线索二叉树中，结点p 没有左子树的充要条件是 。 a. p->lch==NULL b. p->ltag==1 c. p->ltag==1且p->lch=NULL d. 以上都不对 8．在栈操作中，输入序列为（A ，B ，C ，D ），不可能得到的输出序列为：______ A 、（A ， B ， C ， D ） B 、（D ，C ，B ，A ） C 、（A ，C ，D ，B ） D 、（C ，A ，B ，D ） 9．已知某二叉树的后序序列是dabec ，中序序列是debac ，则它的先序序列是 。 A 、acbed B 、decab C 、deabc D 、cedba 10．设矩阵A 是一个对称矩阵，为了节省存储空间，将其下三角部分（见下图）按行序存放在一维数组B[1..n(n-1)/2]中，对任一上三角部分元素)(j i a ij ，在一维数组B 的存放位置是 。 数据结构模拟试题一 一、判断题（每小题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．便于按行处理矩阵元素 数据结构习题19324 习题4-1 1.有六个元素A、B、C、D、E、F依次进栈，允许任何时候出栈，能否得到下列每个序列。 （1）CDBEFA （2）ABEDFC （3）DCEABF （4）BAEFCD 2. 有4个元素a,b,c,d依次进栈，任何时侯都可以出栈，请写出所有可能出栈序列和所有不存在的序列。 3.用一维数组a[7]顺序存储一个循环队列，队首和队尾指针分别用front和rear表示，当前队列中已有五个元素：23，45，67，80，34，其中，23尾队首元素，front的值为3，请画出对应的存储状态，当连续做4次出队运算后，再让15，36，48元素依次进队，请再次画出对应的存储状态。 4. 假定用于顺序存储一个队列的数组的长度为N，队首和队尾指针分别为front和rear，写出求此长度（即所含元素个数）的公式。 习题4-2 算法分析，写出该算法的功能。 1 int AE(int a[],int n) { if(n==0) return 0; else return a[n-1]+AE(a,n-1); } 2.int AF(int k,int s)//第一次使用AF(0,0)调用此算法 { if(s>=100) return k-1; else { k++;s+=k*k;return AF(k,s); } } 3. void Fun1(Stack& s1,int n) { srand(time(0); int i=0,j; while(i 单选题(每题2分，共20分) 1. 1. 对一个算法的评价，不包括如下(B )方面的内容。 A .健壮性和可读性 B .并行性 C .正确性 D .时空复杂度 2.2. 在带有头结点的单链表HL 中，要向表头插入一个由指针 p 指向 的结点，则执行(A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; 都具有相同的(A )。 A.行号 B .列号 C .元素值 D .非零元素个数 9. 快速排序在最坏情况下的时间复杂度为(D )。 A. O(log 2n) B . O(nlog 2n) C . 0(n) D 10.10. 从二叉搜索树中查找一个元素时，其时间复杂度大致 为 A. O(n) B. O(1) C. O(log 2 n) D. O(n 二、 运算题(每题6分，共24分) 1. 1. 数据结构是指数据及其相互之间的 _________________ 。当结点之 间存在M 对N (M N)的联系时，称这种结构为 __________________________ 。 2. 2. 队列的插入操作是在队列的_ _尾 ________ 行，删除操作是在队 列的 ____ 首 _____ 行。 3. 3. 当用长度为N 的数组顺序存储一个栈时，假定用top==N 表示栈 C. p->next=HL; p=HL; 3. 3. A. C. D. HL=p; p-> next=HL; 对线性表，在下列哪种情况下应当采用链表表示? 经常需要随机地存取元素 B. 表中元素需要占据一片连续的存储空间 一个栈的输入序列为1 2 3， 4. 4. 列的是(C ) A. 2 3 1 C. 3 1 2 AOV 网 是一种(D ) 有向 图 B .无向图 (B ) 经常需要进行插入和删除操作 D.表中元素的个数不变 则下列序列中不可能是栈的输出序 B. 3 2 1 5. 5. 6. .无向无环图 D .有向无环图 采用 开放定址法处理散列表的冲突时，其平均查找长度( B. 高于链接法处理冲突 D .高于二分查找 7. 8. 6. A.低于链接法处理冲突 .与链接法处理冲突相同 7. 参数。 A.值 8. B)。 若需要利用形参直接访问实参时，应将形参变量说明为( B .函数 C .指针 D .引用 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点 9. .0(n 2) (C )。 2 ) 模拟试卷一 一、单选题（每题 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. 从逻辑上可以把数据结构分为（）两大类。 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))的结果是（）。 《数据结构》专升本考试试题 (2015年3月) 一、单项选择题(本大题共20小题,每小题2分,共40分) 1.对于一个算法,当输入非法数据时,也要能作出相应的处理,这种要求称为( )。 (A) 正确性 (B) 可行性 (C) 健壮性 (D) 输入性 2.设S为C语言的语句,计算机执行下面算法时,算法的时间复杂度为( )。 for(i=n-1;i>=0;i--) for(j=0;j 一、单项选择题 1 某算法的时间复杂度是O(n 2 ) ，表明该算法（）。 A 问题规模是n2 B 问题规模与n2成正比 C 执行时间等于n2 D 执行时间与n2成正比 2、关于数据结构的描述，不正确的是（）。 A数据结构相同，对应的存储结构也相同。 B数据结构涉及数据的逻辑结构、存储结构和施加其上的操作等三个方面。 C数据结构操作的实现与存储结构有关。 D定义逻辑结构时可不考虑存储结构。 3、按排序策略分来，起泡排序属于（）。 A插入排序B选择排序C交换排序D归并排序 4、利用双向链表作线性表的存储结构的优点是（）。 A便于进行插入和删除的操作 B 提高按关系查找数据元素的速度 C节省空间D便于销毁结构释放空间 5、一个队列的进队顺序为1,2,3,4，则该队列可能的输出序列是（）。 A 1,2,3,4 B 1,3,2,4 C 1,4,2,3 D 4,3,2,1 6、 Dijkstra算法是按（）方法求出图中从某顶点到其余顶点最短路径的。 A按长度递减的顺序求出图的某顶点到其余顶点的最短路径 B按长度递增的顺序求出图的某顶点到其余顶点的最短路径 C通过深度优先遍历求出图中从某顶点到其余顶点的所有路径 D通过广度优先遍历求出图的某顶点到其余顶点的最短路径 7、字符串可定义为n（ n≥ 0）个字符的有限（）。其中，n是字符串的长度，表明字符串中字符的个数。 A集合B数列C序列D聚合 8、在二维数组A[9][10]中，每个数组元素占用 3 个存储单元，从首地址SA 开始按行连续存放。在这种情况下，元素A[8][5]的起始地址为（）。 A SA+141 B SA+144 C SA+222 D SA+255 9、已知广义表为L(A(u,v,(x,y),z),C(m,(),(k,l,n),(())),((())),(e,(f,g),h))，则它的长度是（）。 A2B3C4D5 10.对于具有n(n>1)个顶点的强连通图，其有向边条数至少有_____。 A. n+1 B. n C. n-1 D. n-2 11.一个递归算法必须包括 __________ 。 A. 递归部分 B . 结束条件和递归部分 C. 迭代部分 D. 结束条件和迭代部分 12.从逻辑上看可以把数据结构分为__________两大类。 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 13、若在长度为n 的顺序表的表尾插入一个新元素的渐进时间复杂度为（）。 A O(n) B O(1) C O(n 2) D O(log 2n) 14.采用顺序搜素方式搜索长度为 n 的线性表时，在等概率情况下，搜索成功时的平均搜索 长度为 __________。 A. n B. n/2 C . (n+1)/2 D. (n-1)/2 15、非空的循环单链表first的链尾结点（由p 所指向）满足（）。 A p->link==NULL; B P==NULL; 数据结构设计课程代码：7399 一、单项选择题（在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。每小题2分，共40分） 1、串的长度是（）。 A、串中不同字母的个数 B、串中不同字符的个数 C、串中所含字符的个数，且大于0 D、串中所含字符的个数 2、若用数组S[1..n]作为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（）。 A、S1的栈底位置为0，S2的栈底位置为n+1 B、S1的栈底位置为0，S2的栈底位置为n/2 C、S1的栈底位置为1，S2的栈底位置为n D、S1的栈底位置为1，S2的栈底位置为n/2 3、队列操作的原则是（）。 A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除 4、有64个结点的完全二叉树的深度为（）（根的层次为1）。 A、8 B、7 C、6 D、5 5、在有n个结点的二叉链表中，值为非空的链域的个数为（）。 A、n-1 B、2n-1 C、n+1 D、2n+1 6、带权有向图G用邻接矩阵A存储，则顶点i的人度等于A中（）。 A、第i行非∞的元素之和 B、第i列非∞的元素之和 C、第i行非∞且非0的元素个数 D、第i列非∞且非0的元素个数 7、在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（）。 A、0(n) B、0(log2n) C、0(nolg2n) D、0(n2) 8、若表R在排序前已按键值递增顺序排列，则（）算法的比较次数最少。 A、直接插入排序 B、快速排序 C、归并排序 D、选择排序 9、下列排序算法中，（）排序在某趟结束后不一定选出一个元素放到其最终的位置上。 A、选择 B、冒泡 C、归并 D、堆 填空题（10 * 1’ = 10’） 一、概念题 2.2.当对一个线性表经常进行的是插入和删除操作时，采用链式存储结构为宜。 2.3.当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，最好采用顺序存储结构。 2.6.带头结点的单链表L中只有一个元素结点的条件是L->Next->Next==Null。 3.6.循环队列的引入，目的是为了克服假溢出。 4.2.长度为0的字符串称为空串。 4.5.组成串的数据元素只能是字符。 4.8.设T和P是两个给定的串，在T中寻找等于P的子串的过程称为模式匹配，又称P为模式。 7.2.为了实现图的广度优先搜索，除一个标志数组标志已访问的图的结点外，还需要队列存放被访问的结点实现遍历。 5.7.广义表的深度是广义表中括号的重数 7.8.有向图G可拓扑排序的判别条件是有无回路。 7.9.若要求一个稠密图的最小生成树，最好用Prim算法求解。 8.8.直接定址法法构造的哈希函数肯定不会发生冲突。 9.2.排序算法所花费的时间，通常用在数据的比较和交换两大操作。 1.1.通常从正确性﹑可读性﹑健壮性﹑时空效率等几个方面评价算法的（包括程序）的质量。 1.2.对于给定的n元素，可以构造出的逻辑结构有集合关系﹑线性关系树形关系﹑图状关系四种。 1.3.存储结构主要有顺序存储﹑链式存储﹑索引存储﹑散列存储四种。 1.4.抽象数据类型的定义仅取决于它的一组逻辑特性，而与存储结构无关，即不论其内部结构如何变化，只要它的 数学特性不变，都不影响其外部使用。 1.5.一个算法具有五大特性：有穷性﹑确定性﹑可行性，有零个或多个输入﹑有一个或多个输入。 2.8.在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行下列语句： s->prior= p->prior; s->next= p; p->prior- next= s; p->prior= s;。 2.9.在单链表中设置头结点的作用是不管单链表是否为空表，头结点的指针均不空，并使得对单链表的操作 （如插入和删除）在各种情况下统一。 3.1.队列是限制在表的一端进行插入和在另一端进行删除的线性表，其运算遵循先进先出原则。 3.2.栈是限定尽在表位进行插入或删除操作的线性表。 3.5.在链式队列中，判定只有一个结点的条件是(Q->rear==Q->front)&&(Q->rear!=NULL)。 3.7.已知链队列的头尾指针分别是f和r，则将x入队的操作序列是node *p=(node *)malloc(node); p->next=x; p->next=NULL; if(r) {r->next=p; r=p;} else {r=p; f=p;}。 3.8.循环队列的满与空的条件是(rear+1)%MAXSIZE==fornt和(front=-1&&rear+1==MAXSIZE)。 4.3.串是一种特殊的线性表，其特殊性表现在数据元素都是由字符组成。 4.7.字符串存储密度是串值所占存储位和实际分配位的比值，在字符串的链式存储结构中其结点大小是可变的。 5.3.所谓稀疏矩阵指的是矩阵中非零元素远远小于元素总数，则称该矩阵为矩阵中非零元素远远小于元素总数， 则称该矩阵为稀疏矩阵。 5.4.一维数组的逻辑结构是线性结构，存储结构是顺序存储结构；对二维或多维数组，分别按行优先和列优先两种 不同的存储方式。 7.4.在有向图的邻接矩阵表示中，计算第i个顶点入度的方法是求邻接矩阵中第i列非0元素的个数。 7.10.AOV网中，结点表示活动，边表示活动之间的优先关系，AOE网中，结点表示事件，边表示活动。 9.1.按排序过程中依据不同原则对内部排序方法进行分类，主要有选择排序﹑交换排序﹑插入排序归并排序等4类。 9.3.在堆排序、快速排序和归并排序中若只从排序结果的稳定性考虑，则应选择归并排序方法；若只从平均情况下 排序最快考虑，则应选择快速排序方法；若只从最坏情况下排序最快且要节省类存考虑，则应选择堆排序方法。 9.4.直接插入排序用监视哨的作用是存当前要的插入记录，可又省去查找插入位置时对是否出界的判断。 9.6.设表中元素的初始状态是按键值递增的，则直接插入排序最省时间，快速排序最费时间。 4.9.下列程序判断字符串s是否对称，对称则返回1，否则返回0；如?(“abba”)返回1，?（”abab”）返回0.数据结构专升本模拟题及参考答案讲课教案
专升本试题(数据结构)
数据结构试题库答案
数据结构模拟题(开卷)
数据结构课程教学大纲
山东07年专升本考试数据结构模拟试题.
《数据结构》题库及答案
数据结构模拟试题及答案
数据结构习题19324上课讲义
数据结构试题及答案(10套最新)
《数据结构》模拟试卷一及答案
数据结构专升本模拟题及参考答案讲课教案
专升本试题数据结构
算法与数据结构题库与答案
数据结构模拟试卷(含答案)
最新数据结构课后习题及答案讲课教案
相关主题
文本预览