一、单项选择1.数据结构是一门研究非数值计算的程序设计问题中,数据元素的①C 、数据信息在计算机中的② A 以及一组相关的运算等的课程。

①A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象②A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法2.以下数据结构中, D 是线性结构。

A．广义表Ｂ．二叉树Ｃ．稀疏矩阵Ｄ．串3.从逻辑上可以把数据结构分为 C 两大类。

A．动态结构和静态结构Ｂ．顺序结构和链式结构Ｃ．线性结构和非线性结构Ｄ．初等结构和构造型结构4.以下数据结构中, D 是线性结构。

A．广义表Ｂ．二叉树Ｃ．稀疏矩阵Ｄ．串5.以下数据结构中, D 是非线性结构。

A．栈Ｂ．二叉树Ｃ．队列Ｄ．字符串6.数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是① B 的有限集合，R是D上的② D 有限集合。

①A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．数据对象②A．操作Ｂ．映象Ｃ．存储Ｄ．关系7.线性表的顺序存储结构是一种① A 的存储结构, 线性表的链式存储结构是一种的② B 存储结构。

A．随机存取Ｂ．顺序存取Ｃ．索引存取Ｄ．散列存取.8.线性表的逻辑顺序与存储顺序总是一致的，这种说法__B _。

A. 正确B. 不正确9.下面那一条是顺序存储结构的优点? (A)A . 存储密度大 B. 插入运算方便 C. 删除运算方便D. 可以方便的用于各种逻辑结构的存储表示10.线性表采用链式存储结构时, 要求内存中可用的存储单元的地址.A . 必须是连续的 B. 部分地址必须是连续的 C. 一定不连续D. 连续和不连续都可以11.表长为n的顺序存储的线性表, 当在任何位置上插入和删除一个元素的概率相等时, 插入一个元素所需要移动元素的平均次数为E , 删除一个元素所需要移动元素的平均次数为 AA. (n-1)/2B.nC. n+1D. n-1E. n/2F. (n+1)/2G. (n-2)/212.带头结点的单链表head为空的判定条件是_B___。

A. head= =NULLB. head->next= =NULLC. head->next= =headD. head!=NULL13.在一个单链表中, 若删除p所指向结点的后继结点, 则执行_A___。

A. p->next= p->next->nextB. p=p->next; p->next= p->next->nextC. p= p->next->nextD. p= p->next14.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为_C___。

A. iB. n=iC. n-i+1D. 不确定.15.设栈的输入次序为: 1 , 2, 3, 4, 5, 则不可能是其出栈序列.A. 54321B. 45321C. 43512D. 1234516.一个递归算法必须包括 BA. 递归部分B. 终止条件和递归部分C. 迭代部分D. 终止条件和迭代部分17.用链接方式存储的队列, 在进行删除操作时 DA 仅修改头指针 B. 仅修改尾指针C. 头尾指针都要修改D. 头尾指针可能都要修改18.数组A[m]存放循环队列的元素, 其头尾指针分别是front和rear, 则当前队列的元素个数是__A__。

A. (rear-front+m)%mB. (front-rear+m)%mC. front-rear+1D. rear-front+119.栈和队列的共同特点__C__。

A. 都是先进先出B. 都是先进后出C. 允许在端点插入和删除元素D. 没有共同点20.一个栈的入栈序列a，b，c，d，e，则栈的输出序列是__A__。

A. edcbaB. decbaC. dceabD. abcde21.栈的特点是__B__，队列的特点是__A__。

A. 先进先出B. 先进后出22.从一个栈顶指针HS的链表中删除一个结点, 用x保存被删除的结点值,执行的语句为__C__。

A. x=HS; HS=HS->nextB. HS=HS->next; x=HS->data.C. x=HS->data; HS=HS->nextD. HS->next=HS; x=HS->data23.在链队列Q中, 插入s所指向的结点执行的语句为__C__。

A. Q.front->next=s;B. Q.rear->next=s; Q.rear=sC. s->next=Q.rear;Q.rear=sD. s->next=Q.front;Q.front=s24.空串与空格串是相同的，这种说法__B__。

A. 正确B. 不正确25.下面关于串的叙述, 哪一个是不正确的__B__。

A. 串是字符的有限序列B. 空串是由空格构成的串C. 匹配模式是串的一种重要运算D. 串可以采用链式存储结构26.设有两个串p和q，求q在p中首次出现的位置的运算称作__B__。

A. 连接B. 模式匹配C. 求子串D. 求串长27.若串s='software', 其子串的数目为 BA. 8B. 37C. 36D. 928.二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按行存放时，数组元素A[7][4]的起始地址为__C__。

A. SA+141B. SA+144C. SA+222D. SA+22529.对稀疏矩阵进行压缩存储的目的是__C__.A. 便于进行矩阵运算B. 便于输入输出.C 节省存储空间 D. 降低运算的时间复杂度30.在以下叙述中正确的是 BA.线性表的线性存储结构优于链表存储结构B.二维数组可以看成是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出31.广义表((a),a)的表头为 C , 表尾为 C .A. ()B. aC. (a)D. ((a))32.已知广义表L=((x,y,z),a,(u,t,w)), 从L中取出原子项t的运算为__D__。

A. Head(Tail(Tail(L)))B. Tail(Head(Head(Tail(L))))C. Head(Tail(Head(Tail(L))))D. Head(Tail(Head(Tail(Tail(L)))))33.树最适合用来表示 BA. 有序的数据元素B. 数据之间具有分支层次关系的数据C. 无序的数据元素D. 无太多关系的数据元素34.如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉树的后序为__B__。

A. uwvtsB. vwutsC. wuvtsD. wutsv35.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是__D__。

A. bdgcefhaB. gdbecfhaC. bdgaechfD. gdbehfca36.在一非空二叉树的中序遍历序列中，根结点的右边__A__。

.A. 只有右子树上的所有结点B. 只有右子树上的部分结点C. 只有左子树上的部分结点D. 只有左子树上的所有结点37.设m和n是一棵二叉树上的两个结点, 在中序遍历, n在m前的条件是CA. n在m的右方B. n是m的祖先C. n在m的左方D. n是m的子孙38.深度为5的二叉树至多有__C__个结点。

A. 16B. 32C. 31D. 1039.由权(8,2,5,7)的四个叶子结点构造一棵哈夫曼树, 该树的带权路径长度为DA. 23B. 37C. 46D. 4340.利用二叉链表存储树, 则根结点的右指针是 CA. 指向最左孩子B. 指向最右孩子C. 空D. 非空41.下列存储方式中, 哪一个不是树的存储形式? DA. 双亲表示法B. 孩子链表表示法C. 孩子兄弟表示法D. 顺序存储表示法42.在一个无向图中，所有顶点的度数之和等于所有边数的__C__倍。

A. 1/2B. 1C. 2D. 443.具有n个顶点和多于n-1条边的无向图 B .A. 有可能是树B. 一定不是树C. 一定是树D. 以上答案都不对44.具有6个顶点的无向图至少应有__A__条边才能确保是一个连通图。

.A. 5B. 6C. 7D. 845.无向图G=(V,E), 其中: V={a,b,c,d,e,f}, E={(a,b),(a,e),(a,c), (b,e),(c,f),(f,d),(e,d)}, 则对该图进行深度优先遍历, 得到的序列为: DA. abecdfB. acfebdC. aebcfdD. aedfcb46.下述几种排序方法中，要求内存量最大的是__D__。

A. 插入排序B. 选择排序C. 快速排序D. 归并排序47.排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为__C__。

A. 希尔排序B. 起泡排序C. 插入排序D. 选择排序48.在待排序的元素序列基本有序的前提下，效率最高的排序方法是__A_。

A.插入排序B. 选择排序C. 快速排序D. 归并排序49.下列排序算法中, 哪一个是稳定的排序算法? BA. 直接选择排序B. 二分法插入排序C. 希尔排序D. 快速排序50.将两个各有n个元素的有序表归并成一个有序表, 其最少的比较次数 AA. nB. 2n-1C. 2nD. n-1二、填空题1.算法的五个重要特性是有穷性,确定性,可行性,输入和输出.2.数据的树型结构和图(网)状结构合称非线性结构.3.抽象数据类型的定义仅取决于它的一组逻辑特性, 而与数据在计算机中的表示和实现无关.4.评价算法质量的指标是正确性,易读性,健壮性,高效性..5.数据结构中评价算法的两个重要指标是: 时间复杂度和空间复杂度.6.分析下面算法（程序段），的时间复杂度是__ O (mn) __。

s=0;for (i=0;i<n;i++)for (j=0;j<m;j++)s+=B[i][j];7.当线性表元素的总数基本稳定, 且很少进行删除和插入操作时, 但是要求以最快的速度存取线性表中的元素, 应该采取顺序存储结构.8.顺序表中逻辑上相邻的元素的物理位置必定相邻, 而单链表中逻辑上相邻的元素的物理位置不一定相邻.9.在各个结点查找概率相等的情况下, 从n个结点的单链表中查找一个结点, 平均要访问n/2 个结点.10.在单链表中设置头指针的作用是: 简化操作, 减少边界条件的判断.11.在单链表中, 除首元结点外, 任一结点的存储位置由其直接前驱的指针域指示.12.对于一个具有n个结点的单链表, 在已知p所指向结点后插入一个新结点的时间复杂度是O(1) , 在值域为给定值的结点后插入一个新结点的时间复杂度为O(n).13.在双链表中，每个结点有两个指针域，一个指向_前驱结点__，另一个指向__后继结点_ __。