下载文档原格式
一、选择：(每题2分，共30分) 简单选择排序 冒泡排序 归并排序 稳定1、下列排序算法中，其中（ ）是稳定的。
堆排序 希尔排序 快速排序 基数排序 不稳定A) 堆排序，冒泡排序 B) 快速排序，堆排序 C) 直接选择排序，希尔排序 D) 归并排序，冒泡排序 2、下列排序方法中，哪一个是稳定的排序方法？（ ）A)堆排序 B)二分法插入排序 C)希尔排序 D)快速排序3、一个栈的输入序列为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 4、非空循环链表head 的尾结点 *p 满足下列( )条件A)head->next==p; B)head==p; C)p->next==head; D)p->next==0 5、下列编码中属前缀码的是( )A){1,01,000,001} B){1,01,011,010} C){0,10,110,11} D){0,1,00,11} 6、对于哈希函数H(key)=key % 7,被称为同义词的关键字是( )A)36和50 B)23和39 C)15和44 D)25和517、将一个长度为n 的向量的第i 个元素删除时，需要前移( )个元素。
A) i B) n-i C) n+1 D) n-i+18、有一个有序表为{ 1，3，9，12，32，41，45，62，77，88，92，100}，用折半查找法，若要找62，要经过( )次比较。
A. 3 B. 6 C. 4 D. 5 9、高度为 K 的二叉树最大的结点数为（ ）。
A)2k B)2k-1 C)2k -1 D)2k-1-110、对表长为n 的顺序表进行顺序查找，在查找概率相等的情况下，查找成功的平均查找长度为( )A) (n-1)/2 B) n/2 C) (n+1)/2 D) n11、如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用（ ）A)深度优先搜索算法 B)广度优先搜索算法 C)求最小生成树的prim 算法 D)拓扑排序算法12、已知有向图的正邻接链表的存储结构如下，从顶点1出发的按深度优先遍历序列是( )。
数据结构期末考试题及答案一、单项选择题（每题2分，共20分）1. 在数据结构中，算法的时间复杂度是指（）。
A. 执行算法所需要的计算工作量B. 执行算法所需要的存储空间C. 执行算法所需要的时间D. 执行算法所需要的内存大小答案：A2. 线性表的顺序存储结构和链式存储结构相比，其优点是（）。
A. 插入和删除操作快B. 存储密度高C. 存储空间可以动态分配D. 存储空间利用率高答案：B3. 栈的基本运算中，不包括（）。
A. 入栈B. 出栈C. 取栈顶元素D. 排序答案：D4. 在二叉树的遍历中，先序遍历的顺序是（）。
A. 先根后子B. 先子后根C. 先左后右D. 先右后左答案：A5. 哈希表解决冲突的方法不包括（）。
A. 分离链接法B. 线性探测法C. 链地址法D. 二分查找法答案：D6. 一个图的邻接矩阵表示法中，若第i行第j列的元素为1，则表示（）。
A. 顶点i和顶点j之间有一条边B. 顶点i和顶点j之间没有边C. 顶点i和顶点j之间有n条边D. 顶点i和顶点j之间有m条边答案：A7. 在查找算法中，二分查找法适用于（）。
A. 线性表B. 哈希表C. 树形结构D. 图结构答案：A8. 快速排序算法的时间复杂度在最坏情况下是（）。
A. O(n)B. O(nlogn)C. O(n^2)D. O(2^n)答案：C9. 一个有n个顶点的无向图，其边数最多为（）。
A. nB. n(n-1)/2C. n(n+1)/2D. 2n答案：B10. 以下哪个不是排序算法（）。
A. 冒泡排序B. 选择排序C. 插入排序D. 归并排序答案：D二、填空题（每题2分，共20分）1. 在数据结构中，一个算法的空间复杂度是指算法执行过程中所需要的___________。
答案：存储空间2. 线性表的链式存储结构中，每个节点包含___________和___________。
答案：数据元素，指针3. 栈的特点是___________，___________。
数据结构期末考试试题及答案一、选择题（每题2分，共20分）1. 在数据结构中，算法的时间复杂度是指（）。
A. 编写代码的时间B. 代码的长度C. 执行代码所需的时间D. 执行代码所需的指令条数2. 下列关于队列的描述，错误的是（）。
A. 队列是先进先出（FIFO）的线性表B. 队列允许在一端进行插入操作C. 队列的插入操作称为入队D. 队列的删除操作称为出栈3. 对于长度为n的有序数组，使用二分查找法查找一个元素的平均时间复杂度是（）。
A. O(n)B. O(n^2)C. O(log n)D. O(1)4. 在图的遍历中，深度优先搜索（DFS）使用的数据结构是（）。
A. 栈B. 队列C. 链表D. 数组5. 哈希表的冲突可以通过多种方式解决，以下哪种不是解决冲突的方法？（）A. 开放寻址法B. 链地址法C. 线性探测法D. 排序法6. 一个完全二叉树共有700个节点，它的最大节点数是（）。
A. 700B. 701C. 1400D. 14017. 快速排序算法的最坏情况发生在（）。
A. 每次选择的基准都是最大值B. 数据已经有序C. 数据已经完全逆序D. 所有数据元素相等8. 在一个具有n个节点的二叉搜索树中，最坏情况下查找一个元素的时间复杂度是（）。
A. O(n)B. O(log n)C. O(n^2)D. O(1)9. 堆排序算法中，将一个堆调整为最大堆或最小堆的过程称为（）。
A. 堆调整B. 堆构建C. 堆分解D. 堆维护10. 以下哪个不是B树的特性？（）A. 所有键值都存储在内部节点和叶子节点中B. 所有叶子节点都在同一层上C. 每个内部节点至多有m个子节点D. 每个内部节点的非叶子子节点都至少有m/2个子节点二、简答题（每题5分，共30分）1. 什么是递归？请举例说明递归算法的应用场景。
2. 请简述图的邻接矩阵和邻接表两种存储方式的优缺点。
3. 解释什么是平衡二叉树，并说明它为什么在实际应用中很重要。
数据结构与算法期末考试题及答案一、选择题1. 用于分离由加权无向边组成的完全连通图中连通分量中不相邻顶点的单纯形算法是（C）A. 最小生成树算法B. 广度优先搜索算法C. 最大流算法D. 关键路径算法2. 要设计一个使用图来表示的行业里的公司的决策问题，图的顶点应该表示（B）A. 公司拥有的资源B. 公司所面对的决策选择C. 公司内部的组织结构D. 公司的竞争对手3. 算法的计算时间复杂度O(log2n)中的n表示（A）A. 求解问题规模B. 求解算法所处理的数据量C. 求解问题中所涉及的参数量D. 求解算法所进行的求解步骤4. 以树形结构存储的优先队列中元素出队的操作时间复杂度是（C）A. O(1)B. O(n)C. O(log2n)D. O(n2)5. 以下关于贝尔曼-福特算法的描述错误的是（A）A. 贝尔曼-福特算法是求图 G=(V,E)最小生成树的法B. 贝尔曼-福特算法克服了Prim算法因存储顶点增量重复而带来的内存浪费C. 求解过程中，要维护贝尔曼-福特树中任意两个顶点之间的最短距离D. 贝尔曼-福特算法可以解决单源最短路径问题二、简答题1. 请说明拓扑排序的概念，以及如何使用拓扑排序解决求解关键路径的问题。
拓扑排序是指对有向无环图进行排序，得到一个顶点的线性序列，使得对于图中的每条有向边（u,v），均有u在v之前。
拓扑排序可用于求解关键路径，首先对所有活动按照拓扑排序的方法进行排序，计算该活动的最早开始时间ESi和最晚开始时间LSi，若ESi=LSi，则此活动运行期间不能延迟，为关键活动；若ESi≠LSi，则此活动可以合理推迟，不为关键活动。
请将答案按序写在学校统一印制的专用答题卷上，写在本卷或自备纸上者一律不得分。
一．单项选择题(本题含25个小题，每个小题2分，计50分)二．综合应用题(含5个小题，每小题10分，计50分)1．设LinkList是链表存储结构，试分析下列算法的时间复杂度，并简述程序的主要功能。
void CrList( LinkList &L, int n ){LinkList p, q=L;for ( i =0; i<n; ++i ){p=( LinkList ) malloc( sizeof( int ) );q->next=p;p->data=rand( ); // rand( )：产生一个随机整数q=p;}p->next=NULL;} // 算法结束[参考答案]该算法的时间复杂度主要由for ( i = 0；i < n；++ i )命令决定(即主要由链表长度决定)，因此算法的时间复杂度为O(n)。
程序的主要功能：创建一个含有n个结点的线性链表L，其中数据元素由随机函数产生。
2．画出与下列两个已知遍历序列对应的一颗二叉树：先序遍历序列：A B G E K C F H J D中序遍历序列：G B K E A H F J C D[参考答案]3．已知无向图如下，试绘制一棵从A 点开始的广度优先生成树。
[参考答案]从A 点开始的一棵广度优先生成树如下(六种情况之一)： A →B →C →D 时：A →C →D →B 时：A →D →B →C 时：A →B →D →C 时：A →C →B →D 时：A →D →C →B 时：4．已知关键字集={ 19，23，55，11，30，47，28，38，15，51，42 }，表长m=7，哈希函数H(key)=key%7+1。
试给出由链表地址法产生的哈希地址和哈希链表示意图。
[参考答案]由链表地址法产生的哈希地址是：6，3，7，5，3，6，1，4，2，3，1哈希链表示意图如下：5．设n个整数存放在数组a中。
试题一一、单项选择题（每小题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）6D）8（5）由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为（）。
A）11 B）35 C）19 D）53 以下6-8题基于下图：（6）该二叉树结点的前序遍历的序列为（）。
A）E、G、F、A、C、D、B B）E、A、G、C、F、B、DC）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、DC）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、FC）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,zC）g,m,q,a,n,p,x,h,z D）h,g,m,p,a,n,q,x,z二、（本题8分）对于序列{8,18,6,16,29,28}，试写出堆顶元素最小的初始堆。
《数据结构》期末考试试题及答案一、选择题（每题2分，共20分）1. 下列哪种数据结构是线性结构？A. 栈B. 树C. 队列D. 图答案：A2. 在计算机科学中，什么是最基本的数据结构？A. 数组B. 链表C. 栈D. 树答案：C3. 下列哪种操作的时间复杂度是O(1)?A. 在链表中插入元素B. 在数组中查找元素C. 在树中删除节点D. 在图中寻找最短路径答案：B4. 下列哪种数据结构常常用于实现栈和队列？A. 数组B. 链表C. 树D. 图答案：A5. 下列哪种数据结构是有序的？A. 栈B. 队列C. 链表D. 图答案：C二、填空题（每题2分，共20分）1. 在数据结构中，栈是一种后进先出（____）的数据结构。
答案：线性表2. 队列是一种先进先出（____）的数据结构。
答案：线性表3. 链表是一种____数据结构，由一系列节点组成。
答案：非线性4. 二叉树是一种特殊的树，它的每个节点最多有两个____。
答案：子节点5. 哈希表是通过____函数将关键字映射到表中的位置来访问数据。
答案：哈希三、判断题（每题2分，共20分）1. 树是一种线性结构。
（）答案：错误2. 链表的插入和删除操作时间复杂度都是O(1)。
（）答案：错误3. 图是一种线性结构。
（）答案：错误4. 哈希表是一种基于顺序结构的的数据结构。
（）答案：错误5. 在数据结构中，时间复杂度O(n)表示算法随着输入规模的增加而线性增长。
（）答案：正确四、简答题（每题10分，共30分）1. 请简述栈和队列的特点和应用场景。
答案：栈是一种后进先出（LIFO）的数据结构，应用场景包括函数调用栈、表达式求值等。
队列是一种先进先出（FIFO）的数据结构，应用场景包括任务队列、缓冲区等。
2. 请简述链表的优缺点。
答案：链表的优点包括动态扩容、插入和删除操作时间复杂度为O(1)、可以方便地实现各种复杂数据结构。
缺点包括占用内存空间较大、不如数组支持随机访问。
《数据结构》期末考试试题及答案一、选择题（每题2分，共20分）1. 下列哪一个不是线性结构的基本特征？A. 有且只有一个根结点B. 每个结点最多有一个前驱和一个后继C. 有且只有一个叶子结点D. 有序对中第一个元素是根结点答案：C2. 在单链表中，存储元素的数据域称为元素的哪个部分？A. 指针域B. 数据域C. 结点域D. 头结点答案：B3. 在顺序存储结构中，数据元素之间的逻辑关系由哪个因素决定？A. 数据元素的存储顺序B. 数据元素的存储位置C. 数据元素的类型D. 数据元素的大小答案：A4. 下列哪种排序算法的时间复杂度不是O(nlogn)？A. 快速排序B. 归并排序C. 堆排序D. 冒泡排序答案：D5. 在二叉树中，具有度为2的结点的个数是n0，度为0的结点个数是n2，则有（）。
A. n0 = n2 - 1B. n0 = n2 + 1C. n0 = n2D. n0 = n2 + 2答案：B6. 在线索二叉树中，哪个结点被称为线索结点？A. 有左子树的结点B. 有右子树的结点C. 既没有左子树也没有右子树的结点D. 具有左右子树的结点答案：C7. 在双向链表中，查找结点的时间复杂度是（）。
A. O(1)B. O(n)C. O(nlogn)D. O(n^2)答案：B8. 在栈的操作中，下列哪个操作是非法的？A. 先进先出B. 后进先出C. 可以插入任意元素D. 可以删除任意元素答案：D9. 在顺序表中进行插入操作时，平均移动次数为（）。
A. 0B. n/2C. nD. n-1答案：C10. 在下列排序算法中，哪个算法是不稳定的？A. 冒泡排序B. 快速排序C. 插入排序D. 归并排序答案：B二、填空题（每题2分，共20分）1. 线性表的顺序存储结构称为顺序表，其基本特点是（）。
答案：元素顺序存储2. 在单链表中，每个结点包括两个域：数据域和（）。
答案：指针域3. 在二叉树中，度为0的结点称为（），度为2的结点称为（）。
数据结构期末考试题及答案一、单项选择题（每题2分，共20分）1. 在数据结构中，算法的时间复杂度是指（）。
A. 算法程序的长度B. 算法执行时所需要的基本运算次数C. 算法程序中的语句数D. 算法程序中的指令数答案：B2. 线性表的顺序存储结构和链式存储结构相比，其主要优点是（）。
A. 插入和删除操作快B. 存储密度高C. 存储空间可以动态申请D. 存储空间可以预先分配答案：D3. 在一个长度为n的顺序表中，采用二分查找法查找第k小的元素，最坏情况下需要比较的次数是（）。
A. nB. n/2C. log2(n+1)D. log2n答案：D4. 一个栈的入栈序列为1, 2, 3, 4, 5，下列序列中哪一个不可能是栈的输出序列（）。
A. 5, 4, 3, 2, 1B. 3, 2, 4, 1, 5C. 5, 4, 2, 3, 1D. 1, 2, 5, 3, 4答案：D5. 在二叉树的前序遍历、中序遍历和后序遍历中，根节点总是（）。
A. 第一个被访问B. 第二个被访问C. 第三个被访问D. 最后一个被访问答案：A6. 在一个有n个顶点的无向图中，其边的最大数量是（）。
A. n(n-1)/2B. n(n+1)/2C. n^2D. 2n答案：A7. 哈夫曼编码是一种（）。
A. 静态编码B. 动态编码C. 无损编码D. 有损编码答案：C8. 一个图的邻接矩阵表示法中，若顶点i到顶点j有一条边，则矩阵的第i行第j列的元素为（）。
A. 1B. 0C. 边的权重D. 顶点j的度数答案：C9. 在数据库中，关系模式R(U, F)，其中U={A, B, C, D}，F={(A, B)→C, C→D}，下列哪个关系模式是R的候选键（）。
A. {A, B}B. {A, C}C. {B, C}D. {C, D}答案：A10. 快速排序算法的平均时间复杂度是（）。
A. O(n^2)B. O(nlogn)C. O(n^3)D. O(n)答案：B二、填空题（每题2分，共20分）1. 在数据结构中，递归算法的时间复杂度通常可以用______来描述。
数据结构与算法题库（含参考答案）一、单选题（共100题，每题1分，共100分）1、在一次校园活动中拍摄了很多数码照片，现需将这些照片整理到一个PowerPoint 演示文稿中，快速制作的最优操作方法是：A、创建一个 PowerPoint 相册文件。
B、创建一个 PowerPoint 演示文稿，然后批量插入图片。
C、创建一个 PowerPoint 演示文稿，然后在每页幻灯片中插入图片。
D、在文件夹中选中所有照片，然后单击鼠标右键直接发送到PowerPoint 演示文稿中。
正确答案：A2、下面对“对象”概念描述错误的是A、对象不具有封装性B、对象是属性和方法的封装体C、对象间的通信是靠消息传递D、一个对象是其对应类的实例正确答案：A3、设栈与队列初始状态为空。
首先A,B,C,D,E依次入栈，再F,G,H,I,J 依次入队；然后依次出队至队空，再依次出栈至栈空。
则输出序列为A、F,G,H,I,J,E,D,C,B,AB、E,D,C,B,A,J,I,H,G,FC、F,G,H,I,J,A,B,C,D,E,D、E,D,C,B,A,F,G,H,I,J正确答案：A4、设表的长度为 20。
则在最坏情况下，冒泡排序的比较次数为A、20B、19C、90D、190正确答案：D5、设二叉树的前序序列为 ABDEGHCFIJ，中序序列为 DBGEHACIFJ。
则后序序列为A、DGHEBIJFCAB、JIHGFEDCBAC、GHIJDEFBCAD、ABCDEFGHIJ正确答案：A6、Excel工作表B列保存了11位手机号码信息，为了保护个人隐私，需将手机号码的后 4 位均用“*”表示，以 B2 单元格为例，最优的操作方法是：A、=REPLACE(B2,7,4,"****")B、=REPLACE(B2,8,4,"****")C、=MID(B2,7,4,"****")D、=MID(B2,8,4,"****")第 10 组正确答案：B7、小金从网站上查到了最近一次全国人口普查的数据表格，他准备将这份表格中的数据引用到 Excel 中以便进一步分析，最优的操作方法是：A、通过 Excel 中的“自网站获取外部数据”功能，直接将网页上的表格导入到 Excel 工作表中。
数据结构与算法一选择题1．算法的计算量的大小称为计算的（B ）。
A．效率 B. 复杂性 C. 现实性 D. 难度2．下面说法错误的是（C ）(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)3. 连续存储设计时，存储单元的地址（A ）。
A．一定连续B．一定不连续C．不一定连续D．部分连续，部分不连续4. 下述哪一条是顺序存储结构的优点？（A ）A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示5．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A ）存储方式最节省时间。
A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表6．下面的叙述不正确的是（BC ）A．线性表在链式存储时，查找第i个元素的时间同i的值成正比B. 线性表在链式存储时，查找第i个元素的时间同i的值无关C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关7．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（C ）(1<=i<=n+1)。
A. O(0)B. O(1)C. O(n)D. O(n2)8．双向链表中有两个指针域，llink和rlink，分别指回前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为（D ）A. p＾.llink:=q; q＾.rlink:=p; p＾.llink＾.rlink:=q; q^.llink:=p^.llink;B. q＾.llink:=p^.llink; p＾.llink^.rlink:=q; q＾.rlink:=p; p^.llink:=q^.rlink;C. q^.rlink:=p; p^.rlink:=q; p^.llink^.rlink:=q; q^.rlink:=p;D. p^.llink^.rlink:=q; q^.rlink:=p; q^.llink:=p^.llink; p^.llink:=q;9．下列排序算法中，其中（ D ）是稳定的。
A) 堆排序，冒泡排序B) 快速排序，堆排序C) 直接选择排序，希尔排序D) 归并排序，冒泡排序10．对一组数据（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则采用的排序是( A )。
A) 选择B) 冒泡C) 快速D) 插入11．双向链表中有两个指针域，llink和rlink分别指向前趋及后继，设p指向链表中的一个结点，现要求删去p所指结点，则正确的删除是（D）（链中结点数大于2，p不是第一个结点）A．p^.llink^.rlink:=p^.llink; p^.llink^.rlink:=p^.rlink; dispose(p);B．dispose(p); p^.llink^.rlink:=p^.llink; p^.llink^,rlink:=p^.rlink;C．p^.llink^.rlink:=p^.llink; dispose(p); p^.llink^.rlink:=p^.rlink;D．以上A，B，C都不对。
12.一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（B ）A)CABDEFG B) BCDAEFG C) DACEFBG D) ADBCFEG13. 设一个栈的输入序列是1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（ D ）。
A) 5 1 2 3 4 B) 4 5 1 3 2 C) 4 3 1 2 5 D) 3 2 1 5 414. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（ D ）。
A. i-j-1B. i-jC. j-i+1D. 不确定的15. 一个递归算法必须包括（ B ）。
A. 递归部分B. 终止条件和递归部分C. 迭代部分D.终止条件和迭代部分16. 若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ C ）。
A) 快速排序B) 堆排序C) 归并排序D) 直接插入排序17．下面关于串的的叙述中，哪一个是不正确的？（ B ）A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储18．稳定的排序方法是（ B ）A)直接插入排序和快速排序B)折半插入排序和起泡排序C)简单选择排序和四路归并排序D)树形选择排序和shell排序19．已知串S=‘aaab’,其Next数组值为（A ）。
A．0123 B．1123 C．1231 D．121120．串的长度是指（B ）A．串中所含不同字母的个数B．串中所含字符的个数C．串中所含不同字符的个数D．串中所含非空格字符的个数21. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是（ D ）。
A) a，c，b，d B) b, c，d，a C) c, d，b, a D) d, c，a，b22．数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( A )。
A. 1175B. 1180C. 1205D. 121023．A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（B ）。
A. i（i-1）/2+jB. j（j-1）/2+iC. i（j-i）/2+1D. j（i-1）/2+124. 已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是( C )。
A. head(tail(LS))B. tail(head(LS))C. head(tail(head(tail(LS)))D. head(tail(tail(head(LS))))25．下面说法不正确的是( A )。
A. 广义表的表头总是一个广义表B. 广义表的表尾总是一个广义表C. 广义表难以用顺序存储结构D. 广义表可以是一个多层次的结构26．一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ C ）。
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)27. 已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( D )A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE 28. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B）A．9 B．11 C．15 D．不确定29. 若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用(C)遍历方法最合适。
A．前序B．中序C．后序D．按层次30. 将一个长度为n的向量的第i 个元素删除时，需要前移( B )个元素。
A) i B) n-i C) n+1 D) n-i+131. 某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号，编号为1，2，…，n，且有如下性质：T中任一结点V，其编号等于左子树上的最小编号减1，而V的右子树的结点中，其最小编号等于V左子树上结点的最大编号加1。
这时是按( B )编号的。
A.中序遍历序列B.前序遍历序列C.后序遍历序列D.层次顺序32. 线索二叉树是一种（C ）结构。
A．逻辑B．逻辑和存储C．物理D．线性33. 非空循环链表head 的尾结点*p 满足下列( C )条件A)head->next==p; B)head==p; C)p->next==head; D)p->next==034. 一个栈的输入序列是a,b,c,d,e ，则可能的出栈序列是( D )。
A) ecdab B)cebda C)daecb D)abcde35. 设栈s的类型为sqstack ，判定栈空的条件是( C )。
A) s==NULL B)s->top==0 C)s.top==0 D) s.top==NULL36. 深度为5 的二叉树至多有个( B )结点。
A) 12 B) 31 C) 14 D) 1537. 已知二叉树的后、中根序列分别是bedfca 和badecf，则该二叉树的前根遍历序列是( C )。
A)defbca B)fedbca C) abcdef D)fedcba38. 一个有n个顶点的有向图最多有( B )弧。
A) n(n+1) B) n(n-1) C) n(n+1)/2 D) n(n-1)/239. 具有n个顶点的无向图至少要有( B )条边才有可能是一个连通图。
A) n(n+1) B) n-1 C) n+1 D) n(n-1)40. 图中有关路径的定义是（A ）。
A．由顶点和相邻顶点序偶构成的边所形成的序列B．由不同顶点所形成的序列C．由不同边所形成的序列D．上述定义都不是41. 一个向量的第一个元素的地址是100，每个元素的长度是2 ，则第五个元素的地址是( C )A) 102 B) 110 C) 108 D) 12042. 一个循环顺序队列,队头、尾指针的值分别为front,rear，则队列中元素个数为( A )。
（maxlen为循环顺序表的长度）A) (rear-front+maxlen) % maxlenB) (rear-front) % maxlenC) rear-front+1D) front-rear+143. 一个有n个顶点的图最少有( D )条边。
A) n(n+1) B) n(n-1) C) n(n+1)/2 D) 044. 具有5个顶点的无向图至少要有( A )条边才能确保是一个连通图。
A) 4 B) 5 C) 6 D) 745. 设栈s的类型为sqstack ，最多可容纳maxlen个元素，则判定栈满的条件是( B )。
