数据结构试题A

数据结构期末考试题及答案A2017年数据结构期末考试题及答案一、选择题（共计50 分，每题 2 分，共25题） 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 ．在以下的叙述中，正确的是B 。

A. 线性表的顺序存储结构优于链表存储结构B. 二维数组是其数据元素为线性表的线性表C?栈的操作方式是先进先出D.队列的操作方式是先进后出8．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着A. 数据元素具有同一特点B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致C. 每个数据元素都一样D. 数据元素所包含的数据项的个数要相等9．链表不具备的特点是 A 。

A.可随机访问任一结点B.插入删除不需要移动元素C?不必事先估计存储空间 D.所需空间与其长度成正比10．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用 D 存储方式最节省运算时间。

A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点的双循环链表11．需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。

湖北文理学院 2011－2012 学年度下学期《数据结构与算法》试卷A专业：计算机科学与技术姓名： 学号： 班级：一、判断题（本题共10小题，每小题1分，共计10分）。

（正确的打√，错的打×）1、顺序循环队列Q 空的条件是：Q.front==Q.rear.( )2、关键路径是始点到终点最小长度的路径。

( )3、序列（5, 6, 7, 20, 15, 8, 9, 25, 22，13）是一个堆。

( )4、在插入排序和选择排序中，若原始记录已基本有序，则较适合选用选择排序。

( )5、顺序表是随机存取，存取操作的时间为O （1）。

( )6、已知一棵二叉树的先序序列和后序序列，一定能构造出该二叉树。

() 7、有向图用邻接矩阵表示后，顶点i 的出度等于邻接矩阵中第i 行的元素个数。

( ) 8、归并排序的时间性能不随记录序列中关键字的分布而改变（与初始状态无关）。

( ) 9、在数据结构中，数据的基本单位是数据项。

（）10、对任意一个图，从某顶点出发进行一次广度优先或深度优先遍历，可访问图的所有顶点。

( )二、填空题（本题共10小题，每小题 2 分，共计 20分）。

（请将正确答案填入空格内，答案是确定和唯一的）1、任意一棵具有n 个结点的二叉树，若它有m 个叶子，则该二叉树上度为1的结点数为_____个。

2、常用算法的描述方法有：自然语言 、 、 和流程图。

3、某二叉树的先根遍历序列为IJKLMNO ，中根遍历序列为JLKINMO ，则该二叉树中根结点的右孩子是 。

4、堆排序的时间复杂性为，空间复杂性为。

5、二维数组A[6，7]，按行优先存储，每个元素占2个字节,A基址为600,则元素A[4,5]的存储地址是。

6、对广义表C=（a,（b,c,d））的运算 Tail(Tail(Head((Tail(C))))的结果是。

7、设有一组初始关键字值序列为（49，81，55，36，44，88），则利用快速排序的方法，以第一个关键字值为基准得到的一次划分为_________________________________________。

武汉大学计算机学院2010年－2011学年第一学期“数据结构”考试试题（A）一、单项选择题（每小题2分，共计40分）1. 下列各项中属于逻辑结构的是。

A. 哈希表B. 有序表C. 单链表D. 顺序表2. 以下算法的时间复杂度为。

void fun(int n){ int i=1; while (i<=n) i=i*2; }A. O(n)B. O(n2)C. O(nlog2n)D. O(log2n)3. 在一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动个元素。

A. nB. i-1C. n-iD. n-i+14. 判断带头结点的循环单链表L中只有一个结点的条件是。

A. L==NULLB. L->next==LC. L->next->next==LD. L->next==NULL5. 中缀表达式a*(b+c)-d的后缀表达式是。

A. abcd*+-B. abc+*d-C. abc*+d-D. -+*abcd6. 设环形队列中数组的下标是0～N-1，其头尾指针分别为f和r（f指向队列中队头元素的前一个位置，r指向队尾元素的位置），则其元素个数为。

A. r-fB. r-f-1C. (r-f)％N+1D. (r-f+N)％N7. 若用一个大小为6的数组来实现环形队列，队头指针front指向队列中队头元素的前一个位置，队尾指针rear指向队尾元素的位置。

若当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为。

A. 1和5B. 2和4C. 4和2D. 5和18. 稀疏矩阵采用压缩存储后，通常必会失去功能。

A. 顺序存储B. 随机存取C. 输入输出D. 以上都不对9. 一棵有124个叶子结点的完全二叉树，最多有个结点。

A. 247B. 248C. 249D. 25010. n个结点的线索二叉树上含有的线索个数为。

黑龙江大学信息科学与技术学院第二学历自学考试考试试卷数据结构与算法 课程（形式：闭卷）一、选择题（共20题，每题1分，共20分）1． 在关系R={<01,02>,<01,03>,<01,04>,<02,05>,<02,06>,<03,07>,<03,08>,<03,09>,<04,10>}中，数据元素05，06的前驱是〖 〗。

A) 01 B) 02 C) 03 D) 042．下面用二元组表示的数据结构，属于何种结构〖 〗。

A={K,R}K={a,b,c,d,e,f}R={r}r={<a,b>,<a,c>,<a,d>,<a,e>,<a,f>,<f,e>,<f ,d>,<f,c>,<f,b>,<f,a>}A) 集合结构B) 线性结构 C) 树形结构 D) 图形结构3．在数据类型概念的定义中，数据类型是一种对数据的各方面的描述。

其中包括〖 〗。

A) 数据的来源 B) 数据的排列顺序C) 允许对数据施加的操作 D) 数据的应用4． 顺序存储的线性表L=(a 1,a 2,……,a n )，下列说法正确的是〖 〗。

A) 每个元素都有一个直接前驱和一个直接后继B) 线性表中至少要有一个元素C) 表中元素的排列顺序必须是由小到大或由大到小D) 元素的存储顺序与逻辑顺序相同5．计算一个算法的时间复杂度是指〖 〗。

A)统计一个算法执行时，实际占用的计算机时间B)计算一个算法中的循环步骤的次数C)统计算法中进行简单操作的次数D)一个算法运行时间的相对量度6．在一个长度为n的顺序表中，删除第i个元素(1≤i≤n+1)时，须向前移动的元素的个数是〖〗。

A) n-i B) n-i+1 C) n-i-1 D) i7．对顺序存储的线性表进行排序的有关叙述中，错误的是〖〗。

第二次测试题A-数据结构（C语言）数据结构（C语言）第二次测试A 满分：100分，完成时间：45分钟一、选择题：（每题4分，共28分）1、某二叉树的中序序列和后序序列正好相反，则该二叉树一定是_________的二叉树。

(A)空或只有一个结点 (B)高度等于其结点数 (C)在任一结点无左孩子 (D)任一结点无右孩子 2、n个顶点的无向图的邻接表中结点总数最多有( )个。

(A) 2n (B) n (C) n/2 (D) n(n-1) 3、设连通图G的顶点数为n，则G的生成树的边数为( )。

(A) n (B) n-1 (C) 2n(D) 2n-14、如某数据结构的数据元素的集合为S={A,B,C,D,E,F,G},数据元素之间的关系为R={,,,< D, C >,< G, E>,< G, F >},则该数据结构是一种。

(A)线性结构(B)树结构 (C)图结构 (D)链表结构 5、具有20个结点的二叉树，其深度最多为。

(A)4 (B)5 (C)6 (D)20 6、设一颗二叉树共有50个叶子结点（终端结点），则共有个度为2的结点。

(A)25 (B)49 (C)50 (D)517、在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（） A） eB）2e C） n2-e D）n2-2e二、填空题：（每题2分，共12分）1、一棵哈夫曼树是由5个叶子结点形成的，该哈夫曼树总共有个结点。

2、如果一个有向图有5个顶点，则它最多有条弧。

3、设有1000个元素，用二分法查找时，最大比较次数是。

4、折半查找有序表(2,4,6,12,20,28,38,50,70,100),若查找表中元素12,它依次与表中元素___________________比较大小；若查找55，它依次与表中元素___________________比较大小。

5、深度为8的完全二叉树至少有______个叶子结点。

中国海洋大学命题专用纸（首页）2006学年第 1 学期试题名称：数据结构 (A卷) 共 2 页第 1 页专业年级：学号姓名授课教师分数一、简答下列术语：（10分）1、算法的时间复杂度2、栈与队列的异同3、完全二叉树、二叉排序树二、填空（10分）1、在双向循环链表L中，删除指针P所指结点的语句序列是，，free(p)。

2、将下三角矩阵A[1..8,1..8]的下三角部分逐行地存储到起始地址为1000的内存单元中.已知每个元素占4个单元，则A(6,4)的地址为。

3、高度为5的三阶B－树至少有个结点。

4、分别采用堆排序、快速排序、插入排序和归并排序算法对初始状态已为递增序列的数据表进行递增排序，最省时间的是算法。

三、（8分）已知一棵二叉树的中序序列是dcbgeahfijk，后序序列是dcegbfhkjia，请构造出该二叉树。

四、（10分）假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别是0.07，0.08，0.13，0.22，0.18，0.23,0.04，0.05。

请设计它们相应的哈夫曼编码。

使用0～7的二进制表示形式是另一种编码方案，请比较两种方案的优缺点。

五、（10分）设散列表地址空间为0..6，散列函数为H(x)=i mod 7，其中i为键值x中第一个字母在字母表中的序号，若键值的输入序列为Jen,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec，用链地址法处理冲突，1)构造散列表；2)求出在等概率情况下，查找成功时的平均查找长度。

六、（15分）（1）对下列数据表，写出采用希尔排序算法排序的每一趟的结果。

（100,12,20,31,1,5,44,66,61,200,30,80,150,4,8）（2）对下列数据表，写出采用快速排序算法排序的第一趟的结果。

（70,12,20,150，44,66,61,200,30,80,28）授课教师张海燕命题教师或命题负责人签字院系负责人签字年月日中国海洋大学命题专用纸（附页）if (!m) return 0;n=Paixu(T→rchild); if (!n) return 0;｝return 1;｝。

《数据结构》试题（A卷）（考试时间： 90分钟）一、单项选择题（本大题共15小题，每小题2分，共30分）（每题只有一个选项是正确的,将答案填写在括号内，错选、多选不得分）1.（）是组成数据的基本单位，是一个数据整体中相对独立的单元。

A．数据 B.数据元素 C.数据对象 D.数据结构2.算法计算量的大小称为算法的（）。

A.效率B.复杂度C.数据元素之间的关系D.数据的存储方法3.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入或删除运算，则采用以下（）方式最节省时间。

A.链式存储B. 索引存储C.顺序存储D.散列存储4.下述哪一条是顺序存储结构的优点？（）A.存储密度大B.插入运算方便C.删除运算方便D.可方便地用于各种逻辑结构的存储表示5.在一个单链表中，若删除p所指结点的后续结点，则执行（）。

A.p->next=p->next->nextB.p->next=p->nextC.p=p->next;p->next=p->next->nextD.p=p->next->next6.带头结点的单链表head为空的判定条件是（）。

A.head==NULLB.head->next==NULLC.head->next==headD.head!==NULL7.非空的循环单链表head的尾结点(由p所指向)满足（）。

A.p->head==NULLB.p==NULLC.p->next==headD.p==head8.下面关于线性表的叙述中，错误的是哪一个？（）A.线性表采用顺序存储，必须占用一片连续的存储单元。

B.线性表采用顺序存储，便于进行插入和删除操作。

C.线性表采用链式存储，不必占用一片连续的存储单元。

D.线性表采用链式存储，便于插入和删除操作。

9.队列操作的原则是（）。

A.后进先出B.先进先出C.只能进行插入D.只能进行删除10.栈中允许进行插入和删除的一端称为（）。

数据结构试卷一、填空殖（每空1分共20分)1.数据的物理结构主要包括___顺序存储结构__________和_链式_____________两种情况。

2.设一棵完全二叉树中有500个结点，则该二叉树的深度为_______9___;若用二叉链表作为该完全二叉树的存储结构，则共有______501_____个空指针域.3.设输入序列为1、2、3，则经过栈的作用后可以得到_____6______种不同的输出序列。

4.设有向图G用邻接矩阵A[n][n]作为存储结构，则该邻接矩阵中第i行上所有元素之和等于顶点i的___出度_____,第i列上所有元素之和等于顶点i的____入度____。

5.设哈夫曼树中共有n个结点,则该哈夫曼树中有___0_____个度数为1的结点。

6.设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d,则e和d的关系为____e=d_____。

7.____中序______遍历二叉排序树中的结点可以得到一个递增的关键字序列(填先序、中序或后序）.8.设查找表中有100个元素,如果用二分法查找方法查找数据元素X,则最多需要比较_____7___次就可以断定数据元素X是否在查找表中。

9.不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为______1______。

10.设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号,则第i个结点的双亲结点编号为___i/2_________,右孩子结点的编号为____2i+1_______。

11.设一组初始记录关键字为（72，73,71，23,94,16,5），则以记录关键字72为基准的一趟快速排序结果为_____5 16 71 23 72 94 73______。

12.设有向图G中有向边的集合E=｛〈1，2〉，<2,3>，〈1，4〉，〈4,2>，〈4，3〉｝，则该图的一种拓扑序列为___1 4 2 3___。

数据结构期末考试试题（含答案）2005年－2006学年第⼆学期“数据结构”考试试题（A）姓名学号(序号)_答案隐藏班号要求：所有的题⽬的解答均写在答题纸上（每张答题纸上要写清楚姓名、班号和学号），需写清楚题⽬的序号。

每张答题纸都要写上姓名和序号。

⼀、单项选择题（每⼩题2分，共20分）1．数据的运算a 。

A.效率与采⽤何种存储结构有关B.是根据存储结构来定义的C.有算术运算和关系运算两⼤类D.必须⽤程序设计语⾔来描述答：A。

2.链表不具备的特点是 a 。

A.可随机访问任⼀结点B.插⼊删除不需要移动元素C.不必事先估计存储空间D.所需空间与其长度成正⽐答：参见本节要点3。

本题答案为：A。

3.在顺序表中删除⼀个元素的时间复杂度为 c 。

A.O(1)B.O(log2n)C.O(n)D.O(n2)答：C。

4．以下线性表的存储结构中具有随机存取功能的是d 。

A.不带头结点的单链表B.带头结点的单链表C.循环双链表D.顺序表解D。

5.⼀个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是c 。

A.edcba B.decbaC.dceabD.abcde答：C。

6.循环队列qu的队空条件是 d 。

A. (qu.rear+1)%MaxSize==(qu.front+1)%MaxSizeB. (qu.rear+1)%MaxSize==qu.front+1C.(qu.rear+1)%MaxSize==qu.frontD.qu.rear==qu.front答：D。

7.两个串相等必有串长度相等且 b 。

A.串的各位置字符任意B.串中各位置字符均对应相等C.两个串含有相同的字符D.两个所含字符任意答：B。

8.⽤直接插⼊排序对下⾯四个序列进⾏递增排序，元素⽐较次数最少的是c 。

A.94,32,40,90,80,46,21,69B.32,40,21,46,69,94,90,80C.21,32,46,40,80,69,90,94D.90,69,80,46,21,32,94,40答：C。

2011年——2012年第二学期《数据结构》期末试卷（A）一、选择题：（每小题2分，共30分）1、如果在表示树的孩子兄弟链中有6个空的左指针域，7个空的右指针域，5个结点左、右指针域都为空，则该树中树叶的个数（ B ）A、有7个B、有6个C、有5个D、不能确定2、数据结构是一门研究（ B ）的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。

A、数值计算B、非数值计算C、混合计算D、简单计算3、如果用孩子兄弟链来表示一棵具有n(n>1)个结点的树，则在二叉链表中（ B ）A、至少有n-1个非空的右指针域B、至少有2个空的右指针域C、至少有2个非空的左指针域D、至少有n-1个空的右指针值域4、数据结构在计算机内存中的表示是指（ A ）。

A、数据的存储结构B、数据结构C、数据的逻辑结构D、数据元素之间的关系5、计算机处理的对象之间通常存在着的一种最简单的线性关系，这类数学模型称（ A ）。

A、线性的数据结构B、图的数据结构C、格局D、树型数据结构6、算法的主要任务是分析（ D ）A、算法是否具有较好的可读性B、算法中是否存在语法错误C、算法的功能是否符合设计要求D、算法执行时间和问题规模之间的关系7、用孩子链存储结构表示树，其优点之一是（ D ）比较方便A、判断两个指定结点是不是兄弟B、找指定的结点双亲C、判断指定结点在第几层D、计算指定结点的度数8、线性表采用链式存储结构时，其地址（ D ）A、必须是连续的B、一定是不连续的C、部分地址必须是连续的D、连续与否均可以9、在一个单链表中，删除*p结点之后的一个结点操作是（ D ）A、p next=p;B、p next next=p next;C、p next next=p;D、p next=p next next；10、栈和队列的共同点是（ C ）A、都是先进后出B、都是先进先出C、只允许在端点处插入和删除元素D、没有共同点11、元素ABCD依次进栈后，栈顶元素是（ D ）栈底元素是（A ）A、AB、BC、CD、D12、串是（ D ）A、不少于一个字母的序列B、任意个字母的序列C、不少于一个字符的序列D、有限个字符的序列13、串是一种特殊的线性体现在（ B ）A、可以顺序存储B、数据元素是一个字符C、可以链接存储D、数据元素可以是多个字符14、对于一棵具有n个结点，度为4的树来说，（ A ）。

数据结构试题A答案陕西科技⼤学试题纸（A参考答案及评分标准）课程数据结构班级信息、数学05学号姓名请在每⼩题的四个备选答案中，选出⼀个正确的答案，并将其号码填在括号内。

1.设⼀个栈的输⼊序列为1，2，3，4，则借助⼀个栈所得的输出序列不可能是（D）。

A．1，2，3，4 B．4，3，2，1C．1，3，4，2 D．4，1，2，32. 设有80⾏的⼆维数组A[80][60]，其元素长度为4字节，按⾏优先顺序存储，基地址为300，则元素A[18][25]的存储地址为（D）。

A．3800 B．4376 C．3900 D．47203. 将⼀棵有100个节点的完全⼆叉树从根这⼀层开始，每⼀层上从左到右依次对结点进⾏编号，根节点的编号为0，则编号为49的结点的左孩⼦编号为（B）。

A．98 B．99 C．50 D．494. 在长度为n的顺序存储的线性表中，删除第i个元素（1≤i ≤n）时，需要从前向后依次前移（A）个元素。

A．n-i B．n-i+1 C．n-i-1 D．i5. 栈的插⼊和删除操作在（A）进⾏。

A．栈顶B．栈底C．任意位置D．指定位置6. 链表适⽤于（A）查找。

A．顺序B．⼆分法C．⼆分法、顺序D．随机7. 深度为6(根结点的层次为1)的⼆叉树⾄多有（D）个结点。

A．64 B．32 C．31 D．638. ⽤邻接表表⽰图进⾏⼴度优先遍历时，通常是采⽤（B）来实现算法的。

A．栈B．队列C．树D．图9. 设有两个串ｐ和ｑ，求ｑ在ｐ中⾸次出现的位置的运算称作（B）。

A．连接B．模式匹配C．求⼦串D．求串长10.若某线性表中最常⽤的操作是取第i个数据元素，则采⽤（D）存储⽅式最节省时间。

A．单链表B．双链表C．单向循环D．顺序表11.三个结点可构成（D）个不同形态的⼆叉树。

A．2 B．3 C．4 D．512.下列关键字序列中，（D）是堆。

A．16,72,31,23,94,53 B．94,23,31,72,16,53C．16,53,23,94,31,72 D．16,23,53,31,94,7213.把⼀棵树转换为⼆叉树后，这棵⼆叉树的形态是（A）。

题一二三四五总分总评分人复查人分值40203010100得分湛江师范学院2008年－2009学年度第1学期期末考试试题A卷(考试时间:120分钟)考试科目： 数据结构请将所有答案填写在答题卡上，交卷时请将所有试卷上交一、单选题(每小题2分，共40分)1．下列算法的时间复杂度是（ B ）。

for ( i=0; i<n; i++) c[i][j]=i+j;A O(1)B O(n)C O(log 2n)D O(n 2)2．每一个存储结点不仅含有一个数据元素，还包含一个指针，该存储方式是（ B ）存储方式。

A 顺序B 链式C 索引D 散列3．指针p 指向以L 为头指针的循环链表的首元素的条件是（ A ）。

A p==L B p->next==L C L->next==p D p->next==NULL 4．4个元素进S 栈的顺序是A 、B 、C 、D ，进行两次Pop(S,x)操作后，栈顶元素的值是（ B ）。

A AB BC CD D5．经过下列栈的运算后GetTop(S)的值是（ A ）。

InitStack(s); Push(s,a); Push(s,b); Pop(s); A a B b C 1 D 2（ ）（ ）6．栈的特点是（ B ）。

A 先进先出B 后进先出C 后进后出D 不进不出7．经过下列运算后GetHead(Q)的值是（A ）InitQueue(Q); EnQueue(Q,a); EnQueue(Q,b);A aB bC 1D 28．一维数组的元素起始地址loc[0]=1000，元素长度为4，则loc[2]为（C ）。

A 1000B 1010C 1008D 10209．二叉树第i层上最多有（C ）个结点。

A 2iB 2i-1C 2i-1D i210．满二叉树（A ）二叉树。

A 一定是完全B 不一定是完全C 不是D 不是完全11．二叉树按二叉链表存储，每个结点包含三个域（lchild、data、rchild），若p指针指向二叉树的根结点，经过运算while ( p->rchild!=null ) p=p->rchild，则（A ）。

密封线滨州学院2004—2005学年第一学期期末考试03教育《数据结构》试题（A ）一、单项选择题(在每个小题的四个备选答案中，只有一个答案是正确的，请将正确答案的号码填在题干后的括号内。

每空2分，共30分) 1.一个栈的入栈顺序是ABCDE ，则不可能的出栈顺序是（）A .EDCBA B. DECBA C .DCEAB D. ABCDE 2..在线索二叉树上，线索是什么？ （ ）A 两个标志域B 指向结点前驱和后继的指针C 数据域D 指向左、右子树的指针3.在n 个结点的完全二叉树中，对任一结点I(1<=I<=N)，那么I 的左孩子可能是哪一个？ （ ）A. [I/2]B.2I+1C. 2ID.都不是4.已给如图所示哈夫曼树，那么电文CDAA 的编码是什么？ （ ） A.110100 B.11011100○C.010110111D.11111100 A ○B ○C D5.已给如图所示二叉树，a,b,c,d 分别带权值为7，5，2，4，则该树的带权路径长度是多少？（ ）○A.46B.36C.35D.都不是 ○ ○a b c d6.在图的表示中，哪一种是一种顺序表示法？（ ）A.数组B.邻接表C.十字链表D.邻接多重表7.将一株有100个结点的完全二元树从上到下，从左到右依次进行编号，根结点的编号为1，则编号为49的结点的右孩子编号为（ ）。

A ．98B ．99C ．50D ．没有右孩子8.平衡二叉树上结点的平衡因子不能是哪一个值？ （ ） A.-1 B.0 C.1 D.29.堆排序在最坏情况下，其时间复杂度是多少？ （ ）A.O(2n) B.O(nlogn) C.O(n) D.都不是10．数据在计算机中存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为（ ）。

A ．逻辑结构B ．顺序存储结构C ．链式存储结构D ．以上都对11. 设树T 的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T 中的叶子数为（ ）A ．5B ．6C ．7D ．8 12． 有关二叉树下列说法正确的是（ ）A ．二叉树的度为2B ．一棵二叉树的度可以小于2C ．二叉树中至少有一个结点的度为2D ．二叉树中任何一个结点的度都为213. 下面关于求关键路径的说法不正确的是（ ）。

陕西科技大学试题纸（A参考答案及评分标准）课程数据结构班级信息、数学05学号姓名请在每小题的四个备选答案中，选出一个正确的答案，并将其号码填在括号内。

1.设一个栈的输入序列为1，2，3，4，则借助一个栈所得的输出序列不可能是（D）。

A．1，2，3，4 B．4，3，2，1C．1，3，4，2 D．4，1，2，32. 设有80行的二维数组A[80][60]，其元素长度为4字节，按行优先顺序存储，基地址为300，则元素A[18][25]的存储地址为（D）。

A．3800 B．4376 C．3900 D．47203. 将一棵有100个节点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根节点的编号为0，则编号为49的结点的左孩子编号为（B）。

A．98 B．99 C．50 D．494. 在长度为n的顺序存储的线性表中，删除第i个元素（1≤i ≤n）时，需要从前向后依次前移（A）个元素。

A．n-i B．n-i+1 C．n-i-1 D．i5. 栈的插入和删除操作在（A）进行。

A．栈顶B．栈底C．任意位置D．指定位置6. 链表适用于（A）查找。

A．顺序B．二分法C．二分法、顺序D．随机7. 深度为6(根结点的层次为1)的二叉树至多有（D）个结点。

A．64 B．32 C．31 D．638. 用邻接表表示图进行广度优先遍历时，通常是采用（B）来实现算法的。

A．栈B．队列C．树D．图9. 设有两个串ｐ和ｑ，求ｑ在ｐ中首次出现的位置的运算称作（B）。

A．连接B．模式匹配C．求子串D．求串长10.若某线性表中最常用的操作是取第i个数据元素，则采用（D）存储方式最节省时间。

A．单链表B．双链表C．单向循环D．顺序表11.三个结点可构成（D）个不同形态的二叉树。

A．2 B．3 C．4 D．512.下列关键字序列中，（D）是堆。

A．16,72,31,23,94,53 B．94,23,31,72,16,53C．16,53,23,94,31,72 D．16,23,53,31,94,7213.把一棵树转换为二叉树后，这棵二叉树的形态是（A）。

2008级计算机、软件、网络专业2009—2010学年 第一学期《数据结构》期末试题(A 卷)一、 填空题(20空×1分=20分)1．（ ）是数据的最小单位，（ ）是讨论数据结构是涉及的最小数据单位。

2．在有尾指针rear 指示的循环单链表中，在表尾插入一个结点s 的操作序列是（ ）；删除开始结点的操作序列为（ ）。

3．（ ）可作为实现递归函数调用的一种数据结构。

4．栈和队列是两种特殊的线性表，栈的操作特性是（ ），队列的操作特性是（ ），栈和队列的主要区别在于（ ）。

5．数组通常只有两种运算：存取和（ ），这决定了数组通常采用（ ）结构来实现存储。

6．一棵有(0)n n >个结点的满二叉树共有（ ）个叶子结点和（ ）个非终端结点。

7．图的深度优先遍历类似于树的（ ）遍历，它所用到的数据结构是（ ）。

8．设有一个已按各元素值排好序的线性表，长度为125，用折半查找与给定值相等的元素，若查找成功，则至少需要比较（ ）次，至多需比较（ ）次。

9．对n 个待排序记录序列进行快速排序，所需要的最好时间是（ ），最坏时间是（ ）。

10．一棵5阶B_树中，除根结点外，每个结点的子树数目最少为（ ），最多为（ ）。

二、选择题(10题×2分=20分)1．下面（ ）不是算法所必须具备的特性。

A ．有穷性B ．确切性C ．高效性D ．可行性2．链表不具有的特点是（ ）。

A ．可随机访问任一元素B ．插入、删除不需要移动元素C ．不必事先估计存储空间D ．所需空间与线性表长度成正比3．使用双链表存储线性表，其优点是可以（ ）。

A ．提高检索速度B ．更方便数据的插入和删除C ．节约存储空间D ．很快回收存储空间4．一个栈的入栈序列是1，2，3，4，5，则栈的不可能的输出序列是（ ）。

A ．54321B ．45321C ．43512D ．123455．一个队列的入队顺序是1，2，3，4，则队列的输出顺序是（ ）。

安阳师范学院计信学院信管、计科专升本专业《数据结构》考试2012—2013学年下学期期末考试试卷A一单项选择题（本大题共20小题，每小题1分，共20分） 1．组成数据的基本单位是（ c ）Ａ．数据项 Ｂ．数据类型 C ．数据元素 D ．数据变量2．下面程序段的时间复杂度为（a ）。

for(i=1;i<=n;i++)for(j=i;j<=n;j++) s++; A ．O(1)B ．O(n)C ．O(n )log 2n)D ．O(n 2)3．在一个长度为n 的顺序存储线性表中，向第i 个元素(1≤i ≤n+1)之前插入一个新元素时，需向后移动（ b ）个元素。

A ．n-iB ．n-i+1C ．n-i-1D ．i4．设单链表中指针p 指向结点A ，若要删除A 后的结点且该结点存在，则需要修改指针的操作为（ c ）。

A ．p->next=p->next->nextB ．p=p->nextC ．p=p->next->nextD ．p->next=p5．若让元素1，2，3依次进栈，则出栈次序不可能出现（a ）种情况。

A 、3，2，1B 、2，1，3C 、3，1，2D 、1，3，2 6．在一个循环顺序队列中，队首指针指向队首元素的（ c ）位置。

A 、当前B 、后面C 、前一个D 、后一个7．假定一个链队的队首和队尾指针分别为front 和rear ，则判断队空的条件是（ d ）。

A 、front==NULLB 、front!=NULLC 、rear!=NULLD 、front==rear8．二叉树第i(i ≥1)层最多有（ b ）个结点。

A ．2iB ． 2i-1C ．2iD ．2i -1 9．如果结点A 有3个兄弟，而且B 为A 的双亲，则B 是度为（ a ）Ａ．4 Ｂ．3C ．5D ．1 10．当待排序序列的关键码是随机分布时，下列哪种排序算法的平均时间复杂度最优（ c ）。