1、题号 题型 题目 A B1 J 设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为（ ）。1 22 J设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（）。top=top+1 top=top-13 J 字符串的长度是指（ ）。 串中不同字符的个数 串中不同字母的个数4 J 两个字符串相等的充要条件是（）。 两个字符串的长度相等两个字符串中对应位置上的字符相等5 J设某散列表的长度为100，散列函数H(k)=k % P，则P通常情况下最好选择（ ）。99 976 J设一个顺序有序表A
2、1:14中有14个元素，则采用二分法查找元素A4的过程中比较元素的顺序为（ ）。A1，A2，A3，A4A1，A14，A7，A47 J 设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（ ）。 8 78 J设一棵三叉树中有2个度数为1的结点，2个度数为2的结点，2个度数为3的结点，则该三叉链权中有（ ）个度数为0的结点。5 69 J设无向图G中的边的集合E=(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（ ）。aedfcb acfebd10 J 队列是一种（ ）的线性表。 先进先出 先进后出11 J
3、 下列各种排序算法中平均时间复杂度为O(n2)是（ ）。 快速排序 堆排序12 J设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有（ ）个。4 513 J设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过（ ）次比较。1 214 J设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为（ ）。6 1115 J设有向无环图G中的有向边集合E=，则下列属于该有向图G的一种拓扑排序序列的是（ ）。1，2，3，4 2，3，4，116 J设有一组
4、初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组记录关键字生成的二叉排序树的深度为（ ）。4 517 J设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（）。5，3，4，6，1，23，2，5，6，4，118 J 二叉排序树中左子树上所有结点的值均（ ）根结点的值。 19 J设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（ ）。129 21920 J设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉中共有（ ）个结点。2n n+l21 J
5、设一组初始记录关键字的长度为8，则最多经过（ ）趟插入排序可以得到有序序列。6 722 J设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是（ ）。F，H，C，D，P，A，M，Q，R，S，Y，XP，A，C，S，Q，D，F，X，R，H，M，Y23 J 具有6个顶点的无向图至少应有（）条边才能确保是一个连通图。 5 624 Jmin(A)，函数的返回值是集合A的所有元素中按线性序最小的那个元素。则min(2,3,4)=（ ）。2 325 Jindex(s,t)表示子串定位运算。若串t是串s的子串，则函数返回值是串t在串s中第一次
6、出现的开始位置，否则返回值是0。若s=“ababa“,t=“ba“,则index(s,t)=( )。0 126 J 若串S=software,其子串的数目是（ ）。 8 3727 J 从逻辑上可以把数据结构分为（）两大类。 动态结构、静态结构 顺序结构、链式结构28 J对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）。head=NULL headnext=NULL29 J 链表不具有的特点是（ ）。插入、删除不需要移动元素可随机访问任一元素31 J最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（ ）。(rear+1)MODn=frontrea
7、r=front32 J 栈和队都是（ ）。 顺序存储的 线性结构33 J 输入序列为ABC，可以变为CBA时，经过的栈操作为（ ）。push,pop,push,pop,push,poppush,push,push,pop,pop,pop34 J 算法的计算量的大小称为计算的（）。 效率 复杂性35 J 连续存储设计时，存储单元的地址（）。 一定连续 一定不连续36 J 栈在（ ）中应用。 递归调用 子程序调用37 J 对于栈操作数据的原则是（ ）。 先进先出 后进先出38 J 一个递归算法必须包括（ ）。 递归部分 终止条件和递归部分40 J已知森林F=T1，T2，T3，各棵树Ti(i=1，2
8、，3)中所含结点的个数分别为7，3，5，则与F对应的二叉树的右子树中的结点个数为（ ）。10 1241 J 设S=”abc”;T=”xyz”，则strcmp(S,T)的值为（ ）。 正数 负数42 J 在不完全排序的情况下，就可以找出前几个最大值的方法是（ ）。 快速排序 直接插入排序 43 J 关于哈夫曼树，下列叙述正确的是（）。 可能有度为1的结点 总是完全二叉树 44 J 二叉树的结构如下图所示，其中序遍历的序列为（ ）。 a,b,d,g,c,e,f,h d,g,b,a,e,c,h,f 45 J 将数组称为随机存储结构是因为（）。 数组元素是随机的随时可以对数组元素进行访问46 J 数据
9、结构主要研究（ ）。 数据的逻辑结构 数据的存储结构47 J由于数据的逻辑结构通过不同的存储映像方法可得到不同的存储结构，常见的数据存储结构没有（ ）。邻接存储结构顺序存储结构48 J我们在讨论某种数据结构时，主要讨论四个方面的问题，数据的逻辑结构数据的存储结构在数据的逻辑结构上定义的数据的基本操作；基本操作算法的具体实现；这四个问题的讨论的先后顺序应该是怎样的（ ）。 49 J 用线性链表存储线性表时，要求存储空间（ ）。 必须是连续的 连续不连续都可以 50 J 具有线性结构的数据结构是（ ）。 赫夫曼树 栈51 J 一个栈的入栈序列是abcde，则栈的不可能的输出序列是（ ）。 edcb
10、a decba52 J 非线性结构是数据元素之间存在一种：( )。 一对多关系 多对多关系53 J 数据结构中，与所使用的计算机无关的是数据的( )结构。 存储 物理 54 J 算法分析的目的是( )。 找出数据结构的合理性研究算法中的输入和输出的关系55 J 算法分析的两个主要方面是( )。空间复杂性和时间复杂性正确性和简明性56 J 计算机算法指的是( )。 计算方法 排序方法57 J 计算机算法必须具备输入、输出和（） 等5个特性。可行性、可移植性和可扩充性可行性、确定性和有穷性58 J数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为（ ）。存储结构 逻辑结构59
11、J一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ ）。110 10860 J 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（ ）。访问第i个结点（1in）和求第i个结点的直接前驱（2in）（A）在第i个结点后插入一个新结点（1in）61 J 链接存储的存储结构所占存储空间（）。分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针只有一部分，存放结点值62 J 链表是一种采用（ ）存储结构存储的线性表。 顺序 链式 63 J 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ）。 必须是连续的 部分地址必须是连续的64 J下列算法s
12、uanfa1中语句“x=x*2；“的执行次数是（ ）。void suanfa1(int n) int i,j,x=1；for(i=1；i，则数据结构A是（ ）。线性结构 树型结构73 J下面程序的时间复杂为（ ）。for（i=1，s=0； inext；p-data=q-data；p-next=q-next；free(q)q=p-next；q-data=p-data；p-next=q-next；free(q)75 J设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为（ ）。10，15，14，18，20，36，40，211
13、0，15，14，18，20，40，36，2177 J设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（ ）。n，e e，n78 J 设某强连通图中有n个顶点，则该强连通图中至少有（ ）。条边。 n(n-1) n+179 J设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（）。O(n) O(nlog2n)80 J设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（）。n e81 J 在二叉排序树中插入一个结点的时间复杂度为（ ）。 O(1) O(n)82 J设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排
14、序需要进行（ ）趟的分配和回收才能使得初始关键字序列变成有序序列。3 483 J设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（）。N0=N1+1 N0=Nl+N284 J设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（ ）。log2n+1 log2n-185 J设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（）。O(log2n) O(1)86 J设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为m的结点数为Nm，则N0=（ ）。Nl
15、+N2+Nml+N2+2N3+3N4+(m-1)Nm87 J设连通图G中的边集E=(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)，则从顶点a出发可以得到一种深度优先遍历的顶点序列为（）。abedfc acfebd88 J设输入序列是1、2、3、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是（）。n-i n-1-i89 J 时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是（ ）。 堆排序 冒泡排序90 J 一趟排序结束后不一定能够选出一个元素放在其最终位置上的是（ ）。 堆排序 冒泡排序91 J顺序查找不论在顺序线性表中还是
16、在链式线性表中的时间复杂度为（ ）。O(n) O(n2)92 J 二路归并排序的时间复杂度为（）。 O(n) O(n2)93 J 深度为k的完全二叉树中最少有（）个结点。 2k-1-1 2k-194 J设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（）。front-next=s；front=s；s-next=rear；rear=s；95 J设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（ ）。O(n+e) O(n2)96 J设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度
17、为（ ）。O(n) O(n2)97 J设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（）。第i行非0元素的个数之和第i列非0元素的个数之和98 J 设某无向图有n个顶点，则该无向图的邻接表中有（ ）个表头结点。 2n n99 J 设无向图G中有n个顶点，则该无向图的最小生成树上有（ ）条边。 n n-1100 J程序段s=i=0；do i=i+1；s=s+i；while(iright=s； s-left=p；p-right-left=s；s-right=p-right；s-left=p；s-right=p-right；p-right=s；p-right-left=s；109 J设散列表中有m个存储单元，散列函数H(key)= key % p，则p最好选择（）。小于等于m的最大奇数小于等于m的最大素数110 J 设完全无向图中有n个顶点，则该完全无向图中有（ ）条边。 n(n-1)/2 n(n-1)111 J 设顺序表的长度为n，则顺序查找的平均比较次数为（ ）。 n n/2112 J下列程序段的时间复杂度为（ ）。i=0，s=0； while (snext=p-next；p-next=-sq-next=s； s-next=p
