联大学堂开封大学数据结构网上考试答案
| 设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（ ）。 |
| A.2 B.3 C.4 D.6 |
|
| 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0右孩子的平衡因子为1，则应作（ ）型调整以使其平衡。 |
| A.LL B.LR C.RL D.RR |
|
| 从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（ ）。 |
| A.归并排序 B.冒泡排序 C.插入排序 D.选择排序 |
|
| 对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数最多为（ ）。 |
| A.n+1 B.n C.n-1 D.n(n-1)/2 |
|
| n（n≥2）个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是（ ）。 |
| A.该树一定是一棵完全二叉树 B.树中一定没有度为1的结点 C.树中两个权值最小的结点一定是兄弟结点 D.树中任一非叶结点的权值一定不小于下一层任一结点的权值 |
|
| 对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（ ）遍历实现编号。 |
| A.先序 B. 中序 C.后序 D.从根开始按层次遍历 |
|
| 用链接方式存储的队列，在进行删除运算时（ ）。 |
| A.仅修改头指针 B.仅修改尾指针 C.头、尾指针都要修改 D.头、尾指针可能都要修改 |
|
| 设有数组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 |
|
| 线性表Ｌ在（ ）情况下适用于使用链式结构实现 |
| A.需经常修改Ｌ中的结点值 B.需不断对Ｌ进行删除插入 C.Ｌ中含有大量的结点 D.Ｌ中结点结构复杂 |
|
| 用链接方式存储的队列，在进行删除运算时（ ）。 |
| A.仅修改头指针 B.仅修改尾指针 C. 头、尾指针都要修改 D.头、尾指针可能都要修改 |
|
| 下列关键字序列中，（ ）是堆。 |
| A.16，72，31，23，94，53 B.94，23，31，72，16，53 C.16，53，23，94，31，72 D.16，23，53，31，94，72 |
|
| 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ）。 |
| A.必须是连续的 B.部分地址必须是连续的 C.一定是不连续的 D.连续或不连续都可以 |
|
| 设哈夫曼树中有199个结点，则该哈夫曼树中有（ ）个叶子结点。 |
| A.99 B.100 C.101 D.102 |
|
| 在下列存储形式中，（ ）不是树的存储形式？ |
| A.双亲表示法 B.孩子链表表示法 C.孩子兄弟表示法 D.顺序存储表示法 |
|
| 利用二叉链表存储树，则根结点的右指针是（ ）。 |
| A.指向最左孩子 B.指向最右孩子 C.空 D.非空 |
|
| 若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（ ）遍历方法最合适。 |
| A.前序 B.中序 C.后序 D.按层次 |
|
| 对n个关键字作快速排序，在最坏情况下，算法的时间复杂度是（ ）。 |
| A.O(n) B.O(n2) C.O(nlog2n) D.O(n3) |
|
| 栈和队列的共同点是（ ）。 |
| A.都是先进先出 B.都是先进后出 C.只允许在端点处插入和删除元素 D.没有共同点 |
|
| 从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，这种排序方法称为（ ）。 |
| A.归并排序 B.冒泡排序 C.插入排序 D.选择排序 |
|
| 栈在 （ ）中有所应用。 |
| A.递归调用 B.函数调用 C.表达式求值 D.打印数据缓冲区 |
|
| 评价算法优劣的基本标准有（ ） |
| A.正确性 B.可读性 C.可用性 D.高效性 |
|
| 在下述结论中，正确的是（ ）。 |
| A.只有一个结点的二叉树的度为0; B.二叉树的度为2； C.二叉树的左右子树可任意交换; D.深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 |
|
| 通常对图进行遍历方法（ ）。 |
| A.深度优先遍历 B.广度优先遍历 C.层次遍历 D.中序遍历 |
|
| 广义表((a,b,c,d))的表头是（ ），表尾是（ ）。 |
| A.a B.( ) C.(a,b,c,d) D.(b,c,d) |
|
| 交换二叉树每个结点的左孩子和右孩子。 |
|
|
| 用按层次顺序遍历二叉树的方法，统计树中具有度为1的结点数目。 |
|
|
| 试分析下面各程序段的时间复杂度。i=1; while(i<=n) i=i*3; |
|
|
| 求任意二叉树中第一条最长的路径长度，并输出此路径上各结点的值。 |
|
|
| 借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key的记录。设此组记录存放于数组r[l..n]中。若查找成功，则输出该记录在r数组中的位置及其值，否则显示“not find”信息。请简要说明算法思想并编写算法。 |
|
|
| 分别以邻接矩阵和邻接表作为存储结构，实现以下图的基本操作：① 增加一个新顶点v，InsertVex(G, v)；② 删除顶点v及其相关的边，DeleteVex(G, v);③ 增加一条边，InsertArc(G, v, w);④ 删除一条边，DeleteArc(G, v, w)。 |
|
|
| 如果允许在循环队列的两端都可以进行插入和删除操作。要求：① 写出循环队列的类型定义；② 写出“从队尾删除”和“从队头插入”的算法。 |
|
|
| 试写出折半查找的递归算法。 |
|
|
| 已知两个链表A和B分别表示两个集合，其元素递增排列。请设计算法求出A与B的交集，并存放于A链表中。 |
|
|
| 设从键盘输入一整数的序列：a1, a2, a3，…，an，试编写算法实现：用栈结构存储输入的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。 |
|
|
| 将编号为0和1的两个栈存放于一个数组空间V[m]中，栈底分别处于数组的两端。当第0号栈的栈顶指针top[0]等于-1时该栈为空，当第1号栈的栈顶指针top[1]等于m时该栈为空。两个栈均从两端向中间增长。试编写双栈初始化，判断栈空、栈满、进栈和出栈等算法的函数。双栈数据结构的定义如下：Typedef struct{int top[2],bot[2]; //栈顶和栈底指针 SElemType *V; //栈数组 int m; //栈最大可容纳元素个数}DblStack |
|
|
| 设有顺序放置的n个桶，每个桶中装有一粒砾石，每粒砾石的颜色是红，白，蓝之一。要求重新安排这些砾石，使得所有红色砾石在前，所有白色砾石居中，所有蓝色砾石居后，重新安排时对每粒砾石的颜色只能看一次，并且只允许交换操作来调整砾石的位置。 |
|
|
| 试找出满足下列条件的二叉树① 先序序列与后序序列相同 ②中序序列与后序序列相同③ 先序序列与中序序列相同 ④中序序列与层次遍历序列相同 |
|
|
| 从键盘上输入一个后缀表达式，试编写算法计算表达式的值。规定：逆波兰表达式的长度不超过一行，以$符作为输入结束，操作数之间用空格分隔,操作符只可能有+、-、*、/四种运算。例如：234 34+2*$。 |
|
|
| 有n个记录存储在带头结点的双向链表中，现用双向冒泡排序法对其按上升序进行排序，请写出这种排序的算法。（注：双向冒泡排序即相邻两趟排序向相反方向冒泡）。 |
|
|
| 为什么计算机内一定要配置端口或接口？ |
|
|
| 试分析下面各程序段的时间复杂度。s=0; for i=0; i 教师释疑： O(n2) |
|
|
| 设目标为t=“abcaabbabcabaacbacba”,模式为p=“abcabaa”① 计算模式p的naxtval函数值；② 不写出算法,只画出利用KMP算法进行模式匹配时每一趟的匹配过程。 |
|
|
| 已知字符串S1中存放一段英文，写出算法format(s1,s2,s3,n),将其按给定的长度n格式化成两端对齐的字符串S2, 其多余的字符送S3。 |
|
|
| 设计一个算法，通过一趟遍历在单链表中确定值最大的结点。 |
|
|
| 设二叉树以二叉链表的形式存储，有关类型定义如下：typedef struct BiTNode { // 结点结构 int data; struct BiTNode *lchild, *rchild; // 左右孩子指针} BiTNode, *BiTree;下面是求二叉树上各结点值的和的类_C算法，请填空。int Sum_value( BiTree T ) //T是二叉树的根结点的指针 {} // Sum_value |
|
|
| 利用8255A（端口地址为60H~63H）与打印机相连，完成打印控制功能。8255A的A口作为数据口与打印机连接，采用向量中断方式（连接到8259的IR5）完成工作。设与打印机的连接信号仅有STB#和BUSY两个；8259端口地址为20H~21H，且8259的初始化已经由BIOS程序完成，其ICW2为0AH；8255芯片译码采用74LS138芯片完成。1、 画出连接电路原理图和译码电路图，并说明设计思路。2、编写完整的打印驱动程序。 |
|
|
| 设二叉树以二叉链表的形式存储，有关类型定义如下：typedef struct BiTNode { // 结点结构 int data; struct BiTNode *lchild, *rchild; // 左右孩子指针} BiTNode, *BiTree;下面是求二叉树上叶子结点个数的类_C算法，请填空。int Leaf_number ( BiTree T ) //T是树的根结点的指针 {} // Leaf_number |
|
|
| )已知单链表中结点结构定义如下：typedef int ElemType ;typedef struct LNode { ElemType data; struct LNode *next; } LNode, *Linklist下面是将带头结点的单链有L中值为x的元素全部删除的类_C算法，例如：如果线性表为（20，3，6，18，45，22，18，23），x=18，则操作的结果是：（20，3，6， 45，22，23），请填空。（必要处写出注释）void del_linklist_x ( Linklist &L ,int x)//L为一个带头结点的非空单链表的头指针{} // del_linklist_x |
|
|
| 对22个记录的有序表作折半查找，查找失败时，至少需要比较___个关键字。 |
|
|
| 数据结构是相互之间存在一种或多种特定关系的（ ）的集合。 |
|
|
| 最大容量为n的循环队列，队尾指针是rear，队头是front，若牺牲一个空间不用，则队列满的条件是____________________。 |
|
|
| 算机安全是指计算机财产的安全。计算机财产包括____和____。 |
|
|
| 下面程序段的时间复杂度是（ ）。x=0;for(i=1;i<=n;i=2*i) for(j=1;j<=n;j++) x++; |
|
|
| 非空的线性结构中，有且仅有一个元素没有直接前驱。 |
|
|
| “计算机辅助制造”的英文缩写是____。 |
|
|
| 设一棵二叉树的中序遍历序列为BDCA，后序遍历序列为DBAC，则这棵二叉树的先序遍历序列为____________________。 |
|
|
| 不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。 |
|
|
| 系统软件通常由____、____、____和____等组成。 |
|
|
| 数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（ ）。 |
| A.r-f B.(n+f-r)%n C.n+r-f D.（n+r-f)%n |
|
| 用邻接表表示图进行深度优先遍历时，通常借助（ ）来实现算法。 |
| A.栈 B. 队列 C.树 D.图 |
|
| 若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（ ）种情况。 |
| A.5，4，3，2，1 B.2，1，5，4，3 C.4，3，1，2，5 D.2，3，5，4，1 |
|
| 设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（ ）个。 |
| A.n-1 B.n C.n+1 D.n+2 |
|
| 设哈希表长为14，哈希函数是H(key)=key%11，表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的元素加到表中，用二次探测法解决冲突，则放入的位置是（ ）。 |
| A.8 B.3 C.5 D.9 |
|
| 由3个结点可以构造出多少种不同的二叉树？（ ） |
| A.2 B.3 C.4 D.5 |
|
| 适用于折半查找的表的存储方式及元素排列要求为（ ）。 |
| A.链接方式存储，元素无序 B.链接方式存储，元素有序 C.顺序方式存储，元素无序 D.顺序方式存储，元素有序 |
|
| 若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为（ ）。 |
| A.X的双亲 B.X的右子树中最左的结点 C.X的左子树中最右结点 D.X的左子树中最右叶结点 |
|
| 对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（ ）。 |
| A.(n-1)/2 B.n/2 C.(n+1)/2 D.n |
|
| 折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中（ ）比较大小，查找结果是失败。 |
| A.20，70，30，50 B.30，88，70，50 C.20，50 D.30，88，50 |
|
| 引入二叉线索树的目的是（ ）。 |
| A.加快查找结点的前驱或后继的速度 B.为了能在二叉树中方便的进行插入与删除 C.为了能方便的找到双亲 D.使二叉树的遍历结果唯一 |
|
| 快速排序在下列（ ）情况下最易发挥其长处。 |
| A.被排序的数据中含有多个相同排序码 B.被排序的数据已基本有序 C.被排序的数据完全无序 D.被排序的数据中的最大值和最小值相差悬殊 |
|
| 8254工作在方式1下时,只有在GATE上( ),才可能开始工作 |
| A.为低电平 B.有一正脉冲 C.为高电平 D.有一负脉冲 |
|
| 在数据结构中，从逻辑上可以把数据结构分成（ ）。 |
| A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 |
|
| 顺序存储的线性表的优点是（ ） |
| A.存储密度大 B.插入方便 C.随机存取 D.删除方便 |
|
| 稀疏矩阵的压缩存储形式有（ ） |
| A.十字链表 B.三元组 C.散列 D.索引顺序 |
|
| 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（ ）。 |
| A. (rear+1)%n==front B. rear==front C.rear+1==front D.(rear-l)%n==front |
|
| 深度优先遍历类似于二叉树的（ ）。 |
| A.英语1(20号16：30-18：30) B.中序遍历 C.后序遍历 D.层次遍历 |
|
| 下面关于哈希查找的说法，正确的是（ ）。 |
| A.哈希函数构造的越复杂越好，因为这样随机性好，冲突小 B.除留余数法是所有哈希函数中最好的 C.不存在特别好与坏的哈希函数，要视情况而定 D.哈希表的平均查找长度有时也和记录总数有关 |
|
| 若一组记录的排序码为（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 |
|
| 图的BFS生成树的树高比DFS生成树的树高（ ）。 |
| A.小 B.相等 C.小或相等 D.大或相等 |
|
| 广义表A=(a,b,(c,d),(e,(f,g)))，则Head(Tail(Head(Tail(Tail(A)))))的值为（ ）。 |
| A.(g) B.(d) C.c D.d |
|
| 在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（ ）。 |
| A.访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） B.在第i个结点后插入一个新结点（1≤i≤n） C.删除第i个结点（1≤i≤n） D.将n个结点从小到大排序 |
|
| 串“ababaaababaa”的next数组为（ ）。 |
| A.12345678999 B.12121111212 C.11234223456 D.123012322345 |
|
| 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。 |
| A.13 B.32 C.33 D.40 |
|
| 深度为h的满m叉树的第k层有（ ）个结点。(1= A.mk-1 B.mk-1 C.mh-1 D.mh-1 参考答案：A 参考解析： 暂无 |
| A.mk-1 B.mk-1 C.mh-1 D.mh-1 |
|
| 具有n个顶点的有向图最多有（ ）条边。 |
| A.n B.n(n-1) C.n(n+1) D.n2 |
|
| 假设以行序为主序存储二维数组A=array[1..100,1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5,5]=（ ）。 |
| A.808 B.818 C.1010 D.1020 |
|
| 串的长度是指（ ）。 |
| A.串中所含不同字母的个数 B.串中所含字符的个数 C.串中所含不同字符的个数 D.串中所含非空格字符的个数 |
|
| 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（ ）。 |
| A.i B.n-i C.n-i+1 D.不确定 |
|
| 下面关于B-和B+树的叙述中，不正确的是（ ）。 |
| A.．B-树和B+树都是不平衡的多叉树 B.B-树和B+树都可用于文件的索引结构 C.B-树和B+树都能有效地支持顺序检索 D.B-树和B+树都能有效地支持随机检索 |
|
| 下列排序方法中，（ ）是稳定的排序方法。 |
| A..希尔排序 B..冒泡排序 C..快速排序 D.归并排序 |
|
| 链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（ ）。 |
| A.x=top->data;top=top->link； B.top=top->link;x=top->link C.x=top;top=top->link； D.x=top->link |
|
| 设广义表L=((a,b,c))，则L的长度和深度分别为（ ）。 |
| A.．1和1 B.1和3 C.1和2 D.2和3 |
|
| 若一个栈以向量V[1..n]存储，初始栈顶指针top设为n+1，则元素x进栈的正确操作是( )。 |
| A.top++; V[top]=x; B.V[top]=x; top++; C.top--; V[top]=x; D.V[top]=x; top--; |
|
| 堆是一种（ ）排序。 |
| A.插入 B.选择 C.交换 D.归并 |
|
| 设有一个递归算法如下int fact(int n) { //n大于等于0if(n<=0) return 1;else return n*fact(n-1); } |
| A.n+1 B. n-1 C. n D. n+2 |
|
| 串“ababaabab”的nextval为（ ）。 |
| A.10104101 B.10102101 C.10100011 D.10101011 |
|
| 以下说法错误的是（ ）。 |
| A.求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低 B.顺序存储的线性表可以随机存取 C.由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活 D.线性表的链式存储结构优于顺序存储结构 |
|
| 设二维数组A[1.. m，1.. n]（即m行n列）按行存储在数组B[1.. m*n]中，则二维数组元素A[i,j]在一维数组B中的下标为（ ）。 |
| A.(i-1)*n+j B.(i-1)*n+j-1 C.i*(j-1) D.j*m+i-1 |
|
| 串Ｔ=“abcabaa”，其nextval函数值为：（ ） |
| A.110132 B.111232 C.1110132 D.1111232 |
|
| 下述几种排序方法中，（ ）是稳定的排序方法。 |
| A.希尔排序 B.快速排序 C.归并排序 D.堆排序 |
|
| 已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为item的数据元素。 |
|
|
| 试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）。 |
|
|
| 一个连通图采用邻接表作为存储结构，设计一个算法，实现从顶点v出发的深度优先遍历的非递归过程。 |
|
|
| 试分析下面各程序段的时间复杂度。x=0;for(i=1; i 教师释疑： O(n2) |
|
|
| 试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 |
|
|
| 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点(注意不设头指针) ，试编写相应的置空队、判队空 、入队和出队等算法。 |
|
|
| 设任意n个整数存放于数组A(1:n)中，试编写算法，将所有正数排在所有负数前面（要求算法复杂度为0(n)）。 |
|
|
| 已知f为单链表的表头指针, 链表中存储的都是整型数据，试写出实现下列运算的递归算法： ① 求链表中的最大整数；② 求链表的结点个数；③ 求所有整数的平均值。 |
|
|
| 设二维数组a[1..m, 1..n] 含有m*n 个整数。① 写一个算法判断a中所有元素是否互不相同?输出相关信息(yes/no)；② 试分析算法的时间复杂度。 |
|
|
| 采用邻接表存储结构，编写一个算法，判别无向图中任意给定的两个顶点之间是否存在一条长度为为k的简单路径。 |
|
|
| 已知两个链表A和B分别表示两个集合，其元素递增排列。请设计算法求出两个集合A和B 的差集（即仅由在A中出现而不在B中出现的元素所构成的集合），并以同样的形式存储，同时返回该集合的元素个数。 |
|
|
| 写一个算法统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字符串中的合法字符为A-Z这26个字母和0-9这10个数字）。 |
|
|
| 假设以数组Q[m]存放循环队列中的元素, 同时设置一个标志tag，以tag == 0和tag == 1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。试编写与此结构相应的插入(enqueue)和删除(dlqueue)算法。 |
|
|
| 输出二叉树中从每个叶子结点到根结点的路径。 |
|
|
| 设一组初始记录关键字为(72，73，71，23，94，16，5)，则以记录关键字72为基准的一趟快速排序结果为 。 |
|
|
| 设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有______关系。 |
|
|
| 若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（ ）图。 |
| A.非连通 B.连通 C.强连通 D.有向 |
|
| 对n个不同的关键字由小到大进行冒泡排序，在下列（ ）情况下比较的次数最多。 |
| A.从小到大排列好的 B.从大到小排列好的 C.元素无序 D.元素基本有序 |
|
| 广度优先遍历类似于二叉树的（ ）。 |
| A.先序遍历 B.中序遍历 C.后序遍历 D.层次遍历 |
|
| 一个递归算法必须包括（ ）。 |
| A.递归部分 B.终止条件和递归部分 C. 迭代部分 D.终止条件和迭代部分 |
|
| 快速排序在最坏情况下的时间复杂度为（ ）。 |
| A.O(log2n) B.O(nlog2n) C.0(n) D.0(n2) |
|
| 若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B[1..(n(n+1))/2]中，则在B中确定aij（i A.i*(i-1)/2+j B.j*(j-1)/2+i C.i*(i+1)/2+j D.j*(j+1)/2+i 参考答案：B 参考解析： 暂无 |
| A.i*(i-1)/2+j B.j*(j-1)/2+i C.i*(i+1)/2+j D.j*(j+1)/2+i |
|
| 下列排序算法中，（ ）不能保证每趟排序至少能将一个元素放到其最终的位置上。 |
| A.希尔排序 B.快速排序 C.冒泡排序 D.堆排序 |
|
| 把一棵树转换为二叉树后，这棵二叉树的形态是（ ）。 |
| A.唯一的 B.有多种 C.有多种，但根结点都没有左孩子 D.有多种，但根结点都没有右孩子 |
|
| 二维数组A的每个元素是由10个字符组成的串，其行下标i=0,1,…,8,列下标j=1,2,…,10。若A按行先存储，元素A[8,5]的起始地址与当A按列先存储时的元素（ ）的起始地址相同。设每个字符占一个字节。 |
| A.A[8,5] B.A[3,10] C. A[5,8] D.A[0,9] |
|
| 在单链表中，要将s所指结点插入到p所指结点之后，其语句应为（ ）。 |
| A.s->next=p+1; p->next=s; B.(*p).next=s; (*s).next=(*p).next; C.s->next=p->next; p->next=s->next; D.s->next=p->next; p->next=s; |
|
| 若一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为（ ）。 |
| A.79，46，56，38，40，84 B.84，79，56，38，40，46 C.84，79，56，46，40，38 D.84，56，79，40，46，38 |
|
| 下面关于哈希查找的说法，不正确的是（ ）。 |
| A.采用链地址法处理冲突时，查找一个元素的时间是相同的 B.采用链地址法处理冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的 C.用链地址法处理冲突，不会引起二次聚集现象 D.用链地址法处理冲突，适合表长不确定的情况 |
|
| 为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。 |
| A.队列 B.栈 C. 线性表 D.有序表 |
|
| 堆的形状是一棵（ ）。 |
| A.二叉排序树 B.满二叉树 C.完全二叉树 D.平衡二叉树 |
|
| 在双向链表存储结构中，删除p所指的结点时须修改指针（ ）。 |
| A.p->next->prior=p->prior; p->prior->next=p->next; B.p->next=p->next->next; p->next->prior=p; C.p->prior->next=p; p->prior=p->prior->prior; D.p->prior=p->next->next; p->next=p->prior->prior; |
|
| 串是一种特殊的线性表，其特殊性体现在（ ）。 |
| A.可以顺序存储 B.数据元素是一个字符 C.可以链式存储 D.数据元素可以是多个字符若 |
|
| 数据表中有10000个元素，如果仅要求求出其中最大的10个元素，则采用( )算法最节省时间。 |
| A.冒泡排序 B.快速排序 C.简单选择排序 D.堆排序 |
|
| 链接存储的存储结构所占存储空间（ ）。 |
| A.分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B.只有一部分，存放结点值 C.只有一部分，存储表示结点间关系的指针 D.分两部分，一部分存放结点值，另一部分存放结点所占单元数 |
|
| 下述几种排序方法中，要求内存最大的是（ ）。 |
| A.希尔排序 B.快速排序 C.归并排序 D.堆排序 |
|
| 一个具有1025个结点的二叉树的高h为（ ）。 |
| A.11 B.10 C.11至1025之间 D.10至1024之间 |
|
| 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（ ）。 |
| A.数据具有同一特点 B.不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致 C.每个数据元素都一样 D.数据元素所包含的数据项的个数要相等 |
|
| 在一个图中，所有顶点的度数之和等于图的边数的（ ）倍 |
| A.1/2 B.1 C.2 D.4 |
|
| 将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。 |
| A.n B.2n-1 C.2n D.n-1 |
|
| 折半搜索与二叉排序树的时间性能（ ）。 |
| A.相同 B.完全不同 C.有时不相同 D.数量级都是O(log2n) |
|
