华南农业大学期末考试试卷（A卷）
2011-2012学年第1 学期考试科目：数据结构（JA V A）
考试类型：（闭卷）考试考试时间：120分钟
学号姓名年级专业2010级信管班
答案请写到答题纸上，写在试卷上无效
一、单选题（本大题共10小题，每小题2分，共20分）
1.不考虑优先队列，已知入队序列为{A，B，C，D}，可能的出队序列为：（）
A. {D，B，C，A}
B. {A，B，C，D}
C. {A，D，C，B}
D. {A，C，D，B}
2.已知结点数为1001的完全二叉树，其叶子结点个数为：（）
A.500
B.501
C.602
D.1
3.具有8000个结点的二叉树，其高度至少为：（）
A.10
B.11
C. 12
D.13
4.设一棵哈夫曼树有n个非叶子结点，该树共有（）个节点
A.n
B.2n-1
C.2n+1
D. 2n
5.归并排序的空间复杂度是：（）
A. O（nlog2n）
B. O（n2）
C. O（log2n）
D. O（n）
6.以下程序时间复杂度为:（）
int n=8,m=1024,count=1024;
for (int i=m; i>=1; i--)
count++;
A.O（1）
B. O（m）
C. O（log2m）
D. O（mlog2m）
7.式n+log2n+n*n*n的时间复杂度为：（）
A.O（1）
B. O（n3）
C. O（n+log2n）
D. O（log2n）
8.衡量算法的标准有：（）
A.时间复杂度和空间复杂度
B.输入和输出
C.有穷性和确定性
D.可行性
9.已知入栈顺序为{a,b,c,d,e,f,g},下列哪个是可能的出栈顺序：（）
A. {d,e,c,f,b,g,a}
B. {f,e,g,d,a,c,b}
C. {e,f,d,g,b,c,a}
D. { e,f,d,g,b,a,c }
10.已知一个顺序循环队列最多能容纳60个元素，当前有58个元素时，如果再
插入5个元素，该队列有多少空元素：（）
A.-3
B.63
C.5
D.57
二、填空题（本大题共10小题，每空1分，共20分）
1.软件设计是计算机学科各个领域的核心。软件设计时要考虑的首要问题是数
据的表示、组织和处理方法。______和______是软件系统设计的核心。
2.双链表的插入和删除操作：q = new DLinkNode(x); ______;q.next =
p;p.prev.next = q; ______。
3.两个顺序表相等是指它们各对应______并且______。
4.设一棵二叉树的叶子结点数为n0，2度结点数为n2，则n0=______。N个节
点完全二叉树的高度是______
5.设嵌套广义表Z＝(e, Z)＝(e, (e, (e, (…))))，则Z的长度为______，深度
______。
6.在树结构中，约定根节点的层次为______，其他节点的层次是其父母节点的
层次加______。
7.树的表示法有：图示法、______和______三种。
8.一棵高度为k（k>=0）的完全二叉树是具有至多______个结点的二叉树，一
棵高度为k（k>=0）的满二叉树是具有至少______个结点的二叉树。中根遍历序列和后根遍历序列相反的二叉树是______，由256个权值构造一棵哈夫曼树，则该二叉树共有______结点。
9.由n个顶点组成的无向连通图，最多可以有______条边。
10.10个元素的排序数据序列采用折半查找的平均查找长度是（写出算式）
______。
三、程序分析题 (本题共2小题，每小题8分，共16分)
1.下列该程序片段的运行结果是：____________________。
//import dataStructure.linearList.LinkedStack; //链式栈（略）
public class Exp_bracket
{
public static String isValid(String expstr) //判断expstr表达式中的圆括号是否匹配
{ //返回错误信息LinkedStack
int i=0;
while(i { char ch=expstr.charAt(i); i++; switch(ch) { case '(': stack.push(ch+""); //左括号入栈 break; case ')': if (stack.isEmpty() || !stack.pop().equals("(")) //遇见右括号时，出栈 return "期望("; //判断出栈字符是否为左括号} } if(stack.isEmpty()) return ""; //返回空串表示没有错误 else return "期望)"; } public static void main(String args[]) { String expstr="((1+2)*3+4))("; System.out.println(expstr+" "+isValid(expstr)); expstr="((1+2)*3+4))"; System.out.println(expstr+" "+isValid(expstr)); expstr="((1+2)*3+4)))"; System.out.println(expstr+" "+isValid(expstr)); expstr="(5*4)("; System.out.println(expstr+" "+isValid(expstr)); } } 2. //package dataStructure.tree; //import dataStructure.tree.BinaryNode; //二叉树的二叉链表结点类（略） //import dataStructure.linearList.LinkedQueue; //链式队列（略） //import dataStructure.linearList.LinkedStack; //链式栈（略） //构造并遍历二叉树。 public class BinaryTree_make { public static BinaryTree BinaryTree BinaryNode child_d = new BinaryNode child_b = new BinaryNode child_f = new BinaryNode child_c = new BinaryNode bitree.root = new BinaryNode return bitree; } public static void main(String args[]) { BinaryTree bitree.preOrder(); //先根次序遍历二叉树 bitree.inOrder(); //先根次序遍历二叉树 bitree.postOrder(); //后根次序遍历二叉树 bitree.levelOrder(); //层次遍历二叉树 } } 则程序运行结果如下： 先根次序遍历二叉树（写出字母顺序）：______ 中根次序遍历二叉树（写出字母顺序）：______ 后根次序遍历二叉树（写出字母顺序）：______ 层次遍历二叉树（写出字母顺序）： ______ 四、简答题 (本题共6小题，每小题6分，共36分) 1. 什么是栈和队列？两者有何异同？什么情况下需要使用栈或队列？采用顺序存储结构的栈和队列，在进行插入、删除操作时需要移动数据元素吗？为什么？什么是队列的假溢出？为什么顺序存储结构队列会出现假溢出？怎样解决队列的假溢出问题？链式存储结构队列会出现假溢出吗？顺序存储结构的栈会出现假溢出吗？为什么？ 2. 已知一棵二叉树的中根次序遍历序列为CBDFEGAMLNKJOPRQIHS ，后根次序遍历序列为CFGEDBMNLKRQPOJISHA ，画出这棵二叉树（3分）并进行中序线索化（3分）。 3. 设一段正文由字符集{A,B,C,D,E,F,G ,H}组成，其中每个字符在正文中的出现次数依次为{23,5,17,4,9,31,29,18}，采用Huffman 编码对这段正文进行压缩存储，画出所构造的Huffman 树，并写出每个字符的Huffman 编码（4分）。说明Huffman 编码的特点和作用（2分）。 4. 利用Prim 算法构造以下从A 节点出发的带权无向图的最小生成树，给出该最小生成树的代价。 （a ）带权无向图（b ）最小生成树，代价为45 （c ）Prim 算法不断扩充T ，T 顶点扩充次序为AGBC ……（d ）Kruskal 算法不断合并树，依次选择边(B,G),(A,G),(C,D),(E,F)…… G F 411B A C D E 12 5106G F 4 B A C D E 5 106G F 4B A C D E 12 5 65. 什么是二叉排序树？画出由关键字序列{25,27,30,12,11,18,14,20,15,22}构造的一棵二叉排序树，计算ASL 成功。画出删除节点12，然后再插入节点12后的二叉排序树。 6. 下列removeAll()方法欲删除target 串中所有与pattern 匹配的子串。 public static StringBuffer removeAll(StringBuffer target, String pattern) { int m=target.length(), n=pattern.length(); int i=target.indexOf(pattern), k=i; while (k!=-1) { int j=k+n; k=target.indexOf(pattern, j); while (k>0 && j target.setCharAt(i++, target.charAt(j++)); } return target; } ①对于以下调用语句，运行结果是什么？正确的运行结果是什么？ StringBuffer target = new StringBuffer("ababdabcdabcabc"); System.out.println(removeAll(target, "abc")); 五、程序设计题 (本题共1小题，共8分) //使用顺序表类SeqList求解约瑟夫环问题。 public class Josephus { //创建约瑟夫环并求解，参数指定环长度、起始位置、计数 public Josephus(int number, int start, int distance) { SeqList //采用顺序表存储约瑟夫环的元素，元素类型是字符串，构造方法参数指定顺序表容量 for (int i=0; ①______; i++) ②______; //添加字符串对象 System.out.print("约瑟夫环("+number+","+start+","+distance+")，"); ③______;//输出顺序表的描述字符串 int i = start; //计数起始位置 while (list.length()>1) //多于一个对象时循环 { ④______; System.out.print("删除"+list.remove(i).toString()+"，"); //删除指定位置对象 System.out.println(list.toString()); } System.out.println("被赦免者是"+list.get(0).toString()); } public static void main(String args[]) { new Josephus(5,0,2); } } /* 程序运行结果如下： 约瑟夫环(5,0,2)，(A, B, C, D, E) 删除B，(A, C, D, E) 删除D，(A, C, E) 删除A，(C, E) 删除E，(C) 被赦免者是C */ //注意：泛型 一、单选题（每题 2 分，共20分） 1. 1.对一个算法的评价,不包括如下（B ）方面的内容。 Ａ.健壮性和可读性Ｂ．并行性C。正确性Ｄ．时空复杂度 2.2．在带有头结点的单链表ＨL中,要向表头插入一个由指针p指向 的结点，则执行（A ). Ａ. p－〉ｎｅxt=HL->nexｔ; ＨL-〉nexｔ=p; B． p-〉next=HL；ＨL=p； Ｃ。p-＞ｎext=HＬ； p＝HL；Ｄ. HL=p; ｐ－〉next＝ＨL； 3.3．对线性表,在下列哪种情况下应当采用链表表示？( B ） Ａ.经常需要随机地存取元素 B。经常需要进行插入和删除操作 C。表中元素需要占据一片连续的存储空间D．表中元素的个数不变 4. 4.一个栈的输入序列为１ 2 3，则下列序列中不可能是栈的输出序 列的是( C ） A. 2 3 1 ??? B. ３ 2 1 C。 3 １ 2 ??? D. 1 ２３ 5. 5.AＯV网是一种（D ）。 A．有向图Ｂ．无向图Ｃ．无向无环图D．有向无环图 6.6。采用开放定址法处理散列表的冲突时,其平均查找长度（Ｂ)。 A．低于链接法处理冲突B．高于链接法处理冲突Ｃ.与链接法处理冲突相同 D。高于二分查找 7.7。若需要利用形参直接访问实参时，应将形参变量说明为（D ) 参数. Ａ。值Ｂ。函数 C.指针 D。引用 8.８．在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结 点都具有相同的（ A )。 A。行号 B.列号 C．元素值 D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为( D )。 A。O（loｇ 2n) B．Ｏ（nlog 2 n） C。０（n) D.0 （n2） 10.10.从二叉搜索树中查找一个元素时,其时间复杂度大致为( C ). Ａ．O(n） B. Ｏ(1） C。 O（log 2 n） D. O(n2)二、运算题（每题 6 分，共２４分） 河南理工大学万方学院 2006-2007学年第 2 学期 《数据结构》试卷（A卷） 考试方式：闭卷本试卷考试分数占学生总评成绩的80 % 复查总分总复查人 一、单选题（本题的每一备选答案中， 只有一个是正确的，请把你认为正确的答案 的题号填入题干的括号内，每小题2分，共 30分） 1. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为( )。(1≤i≤n+1) (1) O(0) (2) O(1) (3) O(n) (4) O(n2) 2.在单链表中p所指结点后插入s所指结点,则下列语句正确的是( ) (1) p→next=s; s→next=p; (2) s→next=p→next; p→next=s; (3) s→next=p; p→next=s; (4) p→next=s→next; s→next=p; 3. 设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是( ) （1）A，B，C，D （2）D，C，B，A （3）A，C，D，B （4）D，A，B，C 4.若由树林转化得到的二叉树是非空的二叉树，则二叉树形状是（） （1）根结点无右子树的二叉树（2）根结点无左子树的二叉树 （3）根结点可能有左二叉树和右二叉树（4）根结点只有一个孩子结点的二叉树 5．设二叉树的根为第一层，则深度为i的二叉树结点数最多为（） （1）２i（2）２i+1 （3）２i-１（4）２i -1 6. 首先访问结点的左子树，然后访问该结点，最后访问结点的右子树，这种遍历称为() （1）前序遍历（2）后序遍历（3）中序遍历（4）层次遍历 7．给定下列有向图，从顶点1出发，其广度优先搜索序列为（） （1）12534 （2）12435 （3）14325 （4）12345 8．散列表中的冲突是指（） （1）两个元素具有相同的序号（2）两个元素的关键字相同，而其他属性相同 （3）不同的关键字对应相同的存储地址（4）数据元素的地址相同 9. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址:（） （1）必须是连续的（2）部分地址必须是连续的 （3）一定是不连续的（4）连续或不连续都可以 10．下面程序段的时间复杂度为（） for (int i=1;i 数据结构试卷（一） 一、选择题（20分） 1．组成数据的基本单位是（ 1.C ）。 (A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量 2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（ C ）。 (A) 线性结构(B) 树型结构(C) 图型结构(D) 集合 3．数组的逻辑结构不同于下列（D）的逻辑结构。 (A) 线性表(B) 栈(C) 队列(D) 树 4．二叉树中第i(i≥1)层上的结点数最多有（C）个。 (A) 2i (B) 2i(C) 2i-1(D) 2i-1 5．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（.A ）。 (A) p->next=p->next->next (B) p=p->next (C) p=p->next->next (D) p->next=p 6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（.C ）。 (A) 6 (B) 4 (C) 3 (D) 2 7．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（C ）。 (A) 100 (B) 40 (C) 55 (D) 80 8．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（8.B (A) 3 (B) 4 (C) 5 (D) 1 9．根据二叉树的定义可知二叉树共有（B）种不同的形态。 (A) 4 (B) 5 (C) 6 (D) 7 10.设有以下四种排序方法，则（B ）的空间复杂度最大。 (A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希尔排序 二、填空题(30分) 1.设顺序循环队列Q[0：m-1]的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元 素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F =____________;。 2.设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为___________， 在链式存储结构上实现顺序查找的平均时间复杂度为___________。 3.设一棵二叉树中有n个结点，则当用二叉链表作为其存储结构时，该二叉链表中共有________个指 针域，__________个空指针域。 4.设指针变量p指向单链表中结点A，指针变量s指向被插入的结点B，则在结点A的后面插入结点 B的操作序列为______________________________________。 5.设无向图G中有n个顶点和e条边，则其对应的邻接表中有_________个表头结点和_________个表 结点。 6.设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有______关系。 7.设一棵二叉树的前序遍历序列和中序遍历序列均为ABC，则该二叉树的后序遍历序列为__________。 8.设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编 号为8的双亲结点的编号是___________，编号为8的左孩子结点的编号是_____________。 9.下列程序段的功能实现子串t在主串s中位置的算法，要求在下划线处填上正确语句。 int index(char s[ ], char t[ ]) { i=j=0; while(i 2017年数据结构期末考试题及答案 一、选择题（共计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 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点（由p所指向）满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点 《数据结构》试卷 选择题（从下列答案选项中选出一个正确答案，每小题2分，共22分) 1.在数据结构中，与所使用的计算机无关的是数据的（）结构。 A.逻辑 B.存储 C.逻辑和存储 D.物理 2.若线性表最常用的操作是存取第i个元素及其前驱的值，则采用（）存 储方式节省时间。 A.单链表 B.双链表 C.顺序表 D.单循环链表 3.已知模式串t=“abcaabbcabcaabdab”，该模式串的next数组值为（）。 A.-1，0，0，0，1，1，2，3，0，1，2，3，4，5，6，0，1 B.-1，0，0，0，1，1，2，0，0，1，2，3，4，5，6，0，1 C.-1，1，0，0，1，1，2，0，0，1，2，3，4，5，6，0，1 D.-1，0，0，0，1，1，2，0，0，1，2，3，4，5，6，7，1， 4.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个 元素，其存储地址为1，每个元素占1个地址空间，则a85的地址为（）。 A.13 B.33 C.18 D.40 5.一棵含有101个结点的完全二叉树存储在数组bt[102]中，其中bt[0]不用，若bt[k] 是叶子结点，则k的最小值是（）。 A.51 B.50 C.49 D.48 6.稀疏矩阵一般的压缩存储方法有两种，即（）。 A.二维数组和三维数组 B.三元组表和散列表 C.三元组表和十字链表 D.散列表和十字链表 7.对顺序存储的18个数据元素（A[1]~A[18]）的有序表做二分查找，则查找A[3]的 比较序列的下标为( )。 A.1，2，3 B.9，5，2，3 C.9，5，3 D.9，4，2，3 8.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与 图中的结点的个数有关，而与图的边数无关，这种说法（）。 A.正确 B.错误 9.下列排序算法中，某一趟排序结束后未必能选出一个元素放在最终位置上的是（ ）。 A.堆排序 B.冒泡排序 C.直接插入排序 D.快速排序 10.在平衡二叉树中插入一个结点后造成了不平衡，设最小不平衡子树之根为A,并已 知A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则应作（）型 调整使其平衡。 A.LL B.LR C.RL D.RR 11.在解决计算机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机 将要输出的数据依次写入该缓冲区，而打印机依此从该缓冲区中取出数据打印，该 缓冲区应是一个（）结构。 A.堆栈 B.队列 C.顺序表 D.链表 二、填空题（每空2分，共18分） 1.以下程序段的时间复杂度是________________________，其中n为正整数。 int i=1; while(i<=n) i=i*2; 2.对顺序存储结构的线性表，设表长为n；在等概率假设条件下，插入一个数据元素 需平均移动表中元素______________个；在最坏情况下需移动表中元素 ______________个。 3.设树T的度为4，其中度为1、2、3、4的结点的个数分别为4、3、2、1，则树T 的叶子结点的个数是。 4.判定一个环形队列qu（最多元素为MaxSize）为空的条件是 __________________________________________，判定环形队列qu为满队列的条 数据结构试卷带答案 问题说明 部分题目或答案有问题，现将已经发现的公布如下，同学在作这些模拟题的时候应着重做题方法的理解，遇到问题以教材或课件为准，不确定的地方可找同学商量或问我 （1）试卷1第一套填空题第1题，试卷1第2套选择题第3题关于循环队列队头指针和队尾指针的约定与教材不一致，以教材或课件为准，实际上front指向的是队头元素，rear指向当前尚未被占用的第一个队列空间，队慢或队空的判定条件及入队/出队等操作具体可参考课件或教材 （2）试卷1第一套应用题第5题，不声明邻接点顺序时默认编号最小的邻接点为第一邻接点，该图的深度优先遍历序列为123465,答案错。此外，当给定邻接表时则邻接点顺序按照邻接表中的前后顺序确定，如试卷1第二套填空题第8题 （3）试卷1第五套应用题第4题，两种方法处理冲突的方法下所求ASL值相等都为7/6 （4）试卷1第五套填空题第8题答案给出的是小顶堆需满足的条件，大顶堆满足ki>=k2i p->rlink->llink=p->llink;此外，注意课堂中讲的指针名和操作方法 （12）第4套填空题第6题答案错，设哈夫曼树中共有99个结点，则该树中有____50_____个叶子结点；若采用二叉链表作为存储结构，则该树中有__100___个空指针域。 （13）第5套选择第8题答案应为A:设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为(A) abedfc (14)第5套应用题第3题题目未指明查找方法，没法作 （15）第6套选择第5题应选B，实际是任意结点至多只有一个孩子：设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是(B) 高度等于其结点数 （16）第7套填空1题问题本身错，设指针变量p指向双向链表中的结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为____s->left_____=p；s->right=p->right；___p->right_______=s；s->right->left=s；（设结点中的两个指针域分别为left和right）。（17）第8套填空题第8题答案错 （18）第7套选择第3题题目错，应以60为基准关键字，答案为C．设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键字60为基准而得到的一趟快速排序结果是（）。 (C) 42，40，55，60，80，85 （17）第6套填空9题．快速排序算法的空间复杂度平均情况下为_O(logn)_，最坏的情况下为_O(n)_。(18)第9套填空第3题，题目说循环队列有m个元素实际指循环队列总长为m，此外，该题关于队头和队尾指针的约定不同于教材 （19）第9套填空第4题答案错，9个元素冒泡排序，第一趟比较次数为8，最多8趟 北京师范大学2011～2012学年第 1 学期期末考试试卷（A 卷） 课程名称： 数据结构 任课教师姓名： 刘玉铭 卷面总分： 100 分 考试时长： 100 分钟 考试类别：闭卷 院（系）： 数学科学学院 专 业： 年级： 2010 姓 名： 学 号： 阅卷教师（签字）： 一、 单项选择题（每题2分，共10题20分） 1．以下那一个术语与数据的存储结构无关？ 。 A ．栈 B ．哈希表 C ．线索树 D ．双向链表 2．链表不具有的特点是 。 A ．插入、删除不需要移动元素 B ．可随机访问任一元素 C ．不必事先估计存储空间 D ．所需空间与线性表长度成正比 3．算术表达式a+b*（c+d/e ）转为后缀表达式后为 。 A ．ab+cde/* B ．abcde/+*+ C ．abcde/*++ D ．abcde*/++ 4．二维数组A[10][20]采用列优先的存储方法,若每个元素占2个存储单元，设A[0][0]的地址为100，则元素A[7][6]的存储地址为 。 A ．232 B ．234 C ．390 D ．392 装 订 线 5．若一棵二叉树具有10 个度为2 的结点，5 个度为1 的结点，则度为0 的结点个数是。 A．9 B．11 C．15 D．不确定 6．一棵二叉树中序序列为FEABDC，后序序列为FBADCE，则层序序列为。 A. ABCDEF B. EFCDBA C. FECDAB D. EFCDAB 7．在有向图G 的拓扑序列中，若顶点Vi 在顶点Vj 之前，则下列情形不可能出现的是。 A．G 中有弧 第一章概论 一、选择题 1、研究数据结构就是研究（Ｄ）。 Ａ. 数据的逻辑结构?B。数据的存储结构 C。数据的逻辑结构和存储结构?D．数据的逻辑结构、存储结构及其基本操作(研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作) 2、算法分析的两个主要方面是（Ａ）。 A．空间复杂度和时间复杂度???B。正确性和简单性 C。可读性和文档性D．数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。(线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素,有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继)（链表、栈、队列、数组、串） A. 图Ｂ. 树??C．广义表(线性表的推广) D．栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、（ B ）等5个特性。 Ａ．可执行性、可移植性和可扩充性? B. 可执行性、有穷性和确定性 C。确定性、有穷性和稳定性??? D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C ）。 for(i=0；i 一．是非题 （正确的打“√”，错误的打“×”。） 1. 数据结构可用三元式表示（D，S，P）。其中：D是数据对象，S是D上的关系， P是对D的基本操作集。× 2. 线性表的链式存储结构具有可直接存取表中任一元素的优点。× 3. 字符串是数据对象特定的线性表。 4. 二叉树是一棵结点的度最大为二的树。× 5．邻接多重表可以用以表示无向图，也可用以表示有向图。× 6．可从任意有向图中得到关于所有顶点的拓扑次序。× 7．一棵无向连通图的生成树是其极大的连通子图。× 8．二叉排序树的查找长度至多为log2ｎ。× 9．对于一棵m阶的B-树.树中每个结点至多有m 个关键字。除根之外的所有非终端结点至少有┌m/2┐个关键字。× 10．对于目前所知的排序方法，快速排序具有最好的平均性能。 11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。× 12. 二维数组是其数据元素为线性表的线性表。 13. 连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。× 14. 折半查找不适用于有序链表的查找。 15. 完全二叉树必定是平衡二叉树。 16. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。 17. 队列是与线性表完全不同的一种数据结构。× 18. 平均查找长度与记录的查找概率有关。 19. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。× 20. 算法的时间复杂性越好，可读性就越差；反之，算法的可读性越好，则时间复杂性就越差。× 二．选择题 1. 若对编号为1，2，3的列车车厢依次通过扳道栈进行调度，不能得到 ( e ) 的序列。 a:1,2,3 b:1,3,2 c:2,1,3 d:2,3,1 e:3,1,2 f:3,2,1 2. 递归程序可借助于( b )转化为非递归程序。 a:线性表 b: 栈 c:队列 d:数组 3. 在下列数据结构中( c )具有先进先出（FIFO）特性， ( b )具有先进后出(FILO）特性。 a:线性表 b:栈 c:队列 d:广义表 4. 对字符串s=’data-structure’ 执行操作replace(s,substring(s,6,8),’bas’) 读书破万卷下笔如有神 《数据结构》试卷（A卷） 一、选择题 1. 数据结构是指（）。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 2. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。 A.存储结构 B.逻辑结构 D.顺序存储结构 C. 链式存储结构 3. 树形结构是数据元素之间存在一种（）。 A.一对一关系 B.多对多关系 D. 一对多关系 C.多对一关系 4. 设语句x++的时间是单位时间，则以下语句的时间复杂度为（）。 for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++; 23nn) D.O(C.O(n) B.O( ) A.O(1) 5. 算法分析的目的是（1），算法分析的两个主要方面是（2）。 （1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 （2） A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 6. 计算机算法指的是（1），它具备输入，输出和（2）等五个特性。 （1） A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 （2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性 C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性 7. 数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。 不好说D. 相同C. 高B. 低A. 读书破万卷下笔如有神 8. 数据结构作为一门独立的课程出现是在（）年。 A.1946 B.1953 C.1964 D.1968 9. 数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。 A.正确 B.错误 C.前半句对，后半句错 D.前半句错，后半句对 10. 计算机内部数据处理的基本单位是（）。 A.数据 B.数据元素 C.数据项 D.数据库 11.若查找每个元素的概率相等，则在长度为n的顺序表上查找任一元素的平均查找长度为( )。 《数据结构》试卷B 一、填空题（每空1分，共15分） 1. 向量、栈和队列都是结构，可以在向量的位置插入和删除元素；对于栈 只能在插入和删除元素；对于队列只能在插入和删除元素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为。不允许插入和删除 运算的一端称为。 3. 数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间 的和运算等的学科。 4. 在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。 5. 在具有n个单元的循环队列中，队满时共有个元素。 6. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查 找成功的结点数为；比较四次查找成功的结点数为；平均查找长度为。 二、判断正误（判断下列概念的正确性，并作出简要的说明。）（每小题1分，共10分） （）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（）2. 在表结构中最常用的是线性表，栈和队列不太常用。 （）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。（）5.线性表的逻辑顺序与存储顺序总是一致的 （）6. 栈和队列是一种非线性数据结构。 （）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （）8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 （）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 -精品- 河南理工大学万方学院 2006-2007学年第 2 学期 《数据结构》试卷（A 卷） 考试方式： 闭卷 本试卷考试分数占学 生总评成绩的 80 % 复查总分 总复查人 一、单选题（本题的每一备选答案中，只有一个是正确的，请把你认为正确的答案的题号填入题干的括号内，每小题2分，共30分） 1. 若长度为n 的线性表采用顺序存储结构，在其第i 个位置插入一个新元素的算法的时间复杂度为( )。(1≤i≤n+1) (1) O(0) (2) O(1) (3) O(n) (4) O(n 2) 2.在单链表中p 所指结点后插入s 所指结点,则下列语句正确的是( ) (1) p →next=s; s →next=p; (2) s →next=p →next; p →next=s; (3) s →next=p; p →next=s; (4) p →next=s →next; s →next=p; 3. 设一个栈的输入序列为A ，B ，C ，D ，则借助一个栈所得到的输出序列不可能是( ) （1）A ，B ，C ，D （2）D ，C ，B ，A （3）A ，C ，D ，B （4）D ，A ，B ，C 4.若由树林转化得到的二叉树是非空的二叉树，则二叉树形状是（ ） （1） 根结点无右子树的二叉树 （2） 根结点无左子树的二叉树 （3） 根结点可能有左二叉树和右二叉树 （4） 根结点只有一个孩子结点的二叉树 5．设二叉树的根为第一层，则深度为i 的二叉树结点数最多为（ ） （1）２i （2） ２i +1 （3）２i -１ （4）２i -1 6. 首先访问结点的左子树，然后访问该结点，最后访问结点的右子树，这种遍历称为( ) （1）前序遍历（2）后序遍历（3）中序遍历（4）层次遍历 7．给定下列有向图，从顶点1出发，其广度优先搜索序列为（）（1）12534 （2）12435 （3）14325 （4）12345 8．散列表中的冲突是指（） （1）两个元素具有相同的序号（2）两个元素的关键字相同，而其他属性相同 （3）不同的关键字对应相同的存储地址（4）数据元素的地址相同 9. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址:（） （1）必须是连续的（2）部分地址必须是连续的 （3）一定是不连续的（4）连续或不连续都可以 10．下面程序段的时间复杂度为（） for (int i=1;i 数据结构试题（含答案） 1．数据逻辑结构包括线性结构、树形结构和图状结构三种类型，树形结构和图状结构合称非线性结构 2．数据的逻辑结构分为集合、线性结构、树形结构和图状结构 4种。 3．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有 1 个后续结点。 4．线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 5．在树形结构中，树根结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；叶子结点没． 6．数据结构的基本存储方法是顺序、链式、索引和散列存储。有后续结点，其余每个结点的后续结点可以任意多个。 7．衡量一个算法的优劣主要考虑正确性、可读性、健壮性和时间复杂度与空间复杂度。8．评估一个算法的优劣，通常从时间复杂度和空间复杂度两个方面考察。 9．算法的5个重要特性是有穷性、确定性、可行性、输入和输出。 10．在单链表中，要删除某一指定的结点，必须找到该结点的前驱结点。 11．在单链表中，要删除某一指定的结点，必须找到该结点的前驱结点。 12．在双链表中，每个结点有两个指针域，一个指向前驱结点，另一个指向后继结点。13．在顺序表中插入或删除一个数据元素，需要平均移动 n 个数据元素，移动数据元素的个数与位置有关 14．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表的元素是，应采用顺序存储结构 15．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成单链表和双链表。 16．顺序存储结构是通过下标表示元素之间的关系的；链式存储结构是通过指针表示元素之间的关系的 17．带头结点的循环链表L中只有一个元素结点的条件是 L->next->next=L 18．栈是限定仅在表尾进行插入或删除操作的线性表，其运算遵循后进先出的原则。19．空串是零个字符的串，其长度等于零。空白串是由一个或多个空格字符组成的串，其长度等于其包含的空格个数。 20．组成串的数据元素只能是单个字符。 21．一个子串”str”在主串”datastructure”中的位置是 5 。 22．字符串中任意个连续字符构成的部分称为该串的子串。 23．二维数组M的每个元素是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要 540个字节；M的第8列和第5行共占108个字节24．稀疏矩阵一般的压缩存储方法有两种，即三元组表和十字链表。 25．广义表（（a），（（b），c），（（（d））））的长度是 3 ，深度是 4 。 26．在一棵二叉树中，度为零的结点的个数为n0，度为2 的结点的个数为n2，则有n0＝ n2+1 。 27．在有n个结点的二叉链表中，空链域的个数为__n+1__。 28．一棵有n个叶子结点的哈夫曼树共有__2n-1_个结点 29．深度为5的二叉树至多有 31 个结点。 30．若某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点个数为69 。 《数据结构》试卷 第3 页（共3 页） 河南理工大学万方学院 2006-2007学年第 2 学期 《数据结构》试卷（A 卷） 考试方式： 闭卷 本试卷考试分数占学 生总评成绩的 80 % 复查总分 总复查人 一、单选题（本题的每一备选答案中，只有一个是正确的，请把你认为正确的答案的题号填入题干的括号内，每小题2分，共30分） 1. 若长度为n 的线性表采用顺序存储结构，在其第i 个位置插入一个新元素的算法的时间复杂度为( )。(1≤i≤n+1) (1) O(0) (2) O(1) (3) O(n) (4) O(n 2 ) 2.在单链表中p 所指结点后插入s 所指结点,则下列语句正确的是( ) (1) p →next=s; s →next=p; (2) s →next=p →next; p →next=s; (3) s →next=p; p →next=s; (4) p →next=s →next; s →next=p; 3. 设一个栈的输入序列为A ，B ，C ，D ，则借助一个栈所得到的输出序列不可能是( ) （1）A ，B ，C ，D （2）D ，C ，B ，A （3）A ，C ，D ，B （4）D ，A ，B ，C 4.若由树林转化得到的二叉树是非空的二叉树，则二叉树形状是（ ） （1） 根结点无右子树的二叉树 （2） 根结点无左子树的二叉树 （3） 根结点可能有左二叉树和右二叉树 （4） 根结 点只有一个孩子结点的二叉树 5．设二叉树的根为第一层，则深度为i 的二叉树结点数最多为（ ） （1）２i （2） ２ i +1 （3）２ i -１ （4）２i -1 6. 首先访问结点的左子树，然后访问该结点，最后访问结点的右子树，这种遍历称为( ) （1）前序遍历（2）后序遍历（3）中序遍历（4）层次遍历 7．给定下列有向图，从顶点1出发，其广度优先搜索序列为（）（1）12534 （2）12435 （3） 14325 （4）12345 8．散列表中的冲突是指（） （1）两个元素具有相同的序号（2）两个元素的关键字相同，而其他属性相同 （3）不同的关键字对应相同的存储地址（4）数据元素的地址相同 9. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址:（） （1）必须是连续的（2）部分地址必须是连续的（3）一定是不连续的（4）连续或不连续都可以 10．下面程序段的时间复杂度为（） for (int i=1;i 一、判断题： 1、线性表的逻辑顺序与物理顺序总是一致的。( ) 2、线性表的顺序存储表示优于链式存储表示。( ) 3、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。( ) 4、二维数组是其数组元素为线性表的线性表。( ) 5、每种数据结构都应具备三种基本运算：插入、删除和搜索。( ) 6、数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个 方面。( ) 7、线性表中的每个结点最多只有一个前驱和一个后继。（） 8、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。（） 9、栈和队列逻辑上都是线性表。（） 10、单链表从任何一个结点出发，都能访问到所有结点（） 11、删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。（） 12、快速排序是排序算法中最快的一种。（） 13、多维数组是向量的推广。（） 14、一般树和二叉树的结点数目都可以为0。（） 15、直接选择排序是一种不稳定的排序方法。（） 16、98、对一个堆按层次遍历，不一定能得到一个有序序列。（） 17、在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。（） 18、折半搜索只适用与有序表，包括有序的顺序表和有序的链表。（） 19、堆栈在数据中的存储原则是先进先出。（） 20、队列在数据中的存储原则是后进先出。（） 21、用相邻矩阵表示图所用的存储空间大小与图的边数成正比。（） 22、哈夫曼树一定是满二叉树。（） 23、程序是用计算机语言表述的算法。（） 24、线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。（） 25、用一组地址连续的存储单元存放的元素一定构成线性表。（） 26、堆栈、队列和数组的逻辑结构都是线性表结构。（） 27、给定一组权值，可以唯一构造出一棵哈夫曼树。（） 28、只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。（） 《数据结构》试卷及答案 1．算法分析的目的是( )。 A.找出数据结构的合理性 B.研究算法中输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2．（）是具有相同特性数据元素的集合，是数据的子集。 A.数据符号 B.数据对象 C.数据 D.数据结构 3．用链表表示线性表的优点是( )。 A.便于随机存取 B.花费的存储空间比顺序表少 C.便于插入与删除 D.数据元素的物理顺序与逻辑顺序相同 4．输入序列为（A,B,C,D）不可能的输出有（）。 A.(A,B,C,D) B. (D,C,B,A) C. (A,C,D,B) D . (C,A,B,D) 5．在数组表示的循环队列中，front、rear分别为队列的头、尾指针，maxSize为数组的最大长度，队满的条件是( )。 A. front=maxSize B. (rear+1)%maxSize=front C. rear=maxSize D. rear=front 6．设有串t='I am a good student '，那么Substr(t,6,6)=（）。 A. student B. a good s C. good D. a good 7．设有一个对称矩阵A，采用压缩存储方式，以行序为主序存储a11为第一个元素，其存储地址为1，每个元素占一个地址空间，则a85地址为（）。 A.23 B.33 C.18 D. 40 8．已知广义表LS=(A,(B,C,D),E)运用head和tail函数，取出LS中原子b的运算（）。 A. Gethead(Gethead(LS)) B. Gettail(Gethead(LS)) C. Gethead(Gethead(Gettail(LS))) D. Gethead(Gettail(LS)) 9．若已知一棵二叉树先序序列为ABCDEFG，中序序列为CBDAEGF，则其后序序列为( ) A. CDBGFEA B. CDBFGEA C. CDBAGFE D. BCDAGFE 10．下列存储形式中，( ) 不是树的存储形式。 A.双亲表示法 B.左子女右兄弟表示法 C.广义表表示法 D.顺序表示法 11．对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是( )。 A.直接选择排序 B.直接插入排序 C.快速排序 D.起泡排序 12．采用折半查找方法进行查找，数据文件应为（），且限于（）。数据结构试题及答案10套
数据结构试卷A
数据结构试卷带答案
2017年数据结构期末考试题及答案A
数据结构A卷试题及答案
数据结构试卷带答案
数据结构试卷-A+答案
数据结构试题及答案
数据结构试题(含答案)
数据结构试卷A卷
数据结构试卷B卷(含答案)
数据结构试卷A
数据结构试题(含答案)
数据结构试卷A
数据结构试题及答案
数据结构试卷及答案压缩版
相关主题
文本预览