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

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

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

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

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

A •栈 E.二叉树C•队列 D.字符串6. 数据结构DS(Data StrUCt)可以被形式地定义为DS= ( D, R),其中D是①_B_的有限集合，R是D上的②_有限集合。

①A•算法 E •数据元素 C •数据操作 D •数据对象② A •操作 E •映象 C •存储 D •关系7. 线性表的顺序存储结构是一种①丄的存储结构，线性表的链式存储结构是一种的②—B—存储结构。

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

A. head= =NULLB. head-> next= =NULLC. head-> next= =headD. head!=NULL13. 在一个单链表中,若删除P 所指向结点的后继结点,则执行_A__A. p->n ext= p->n ext- >n extB. P=P->n ext; p->n ext= p->n ext- >nextC. P= p->n ext- >n extD. P= p->n ext,插入一个元素所需要移动元素的平均次数为14. 若已知一个栈的入栈序列是1， 2， 3, A. i B. n=i C. n-i+1 …，n ,其输出序列为p1, p2, p3,∙∙∙, pn ,D.不确定若 p1= n ,贝U Pi 为 C 。

21. 栈的特点是_B__,队列的特点是__AA.先进先出B.先进后出22. 从一个栈顶指针HS 的链表中删除一个结点,用X 保存被删除的结点值，执行的语句为__CA. x=HS; HS=HS->n extB. HS=HS->n ext; x=HS->data15. ___________________________________ 设栈的输入次序为：1 , 2, 3, 4, 5,则 ____________________________ 不可能是其出栈序列16. 一个涕归算法必须包括 BA.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分17. 用链接方式存储的队列,在进行删除操作时 DA 仅修改头指针 B.仅修改尾指针C.头尾指针都要修改D.头尾指针可能都要修改18. 数组A[m]存放循环队列的元素，其头尾指针分别是front 和rear,则当前队列的元素个数是A. (rear-fro nt+m)%mB. (fron t-rea )%mC. fron t-rear+1D. rear-fr On t+119. 栈和队列的共同特点—__。

A.都是先进先出B.都是先进后出C.允许在端点插入和删除元素D.没有共同点20. 一个栈的入栈序列a ，b , c , A. edcba B. decba d , e ,贝U 栈的输出序列是 一AC. dceabD. abcdeC. x=HS->data; HS=HS->nextD. HS->n ext=HS; x=HS->data23. 在链队列Q中,插入S所指向的结点执行的语句为_C__。

A. Q.front->n ext=s;B. Q.rear- >n ext=s; Q.rear=sC. s->n ext=Q.rear;Q.rear=sD. s->n ext=Q.fr On t;Q.fro nt=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.有序的数据元素 C.无序的数据元素 34. 如果某二叉树的前根次序遍历结果为StuWV ,中序遍历为UWtVS ,那么该二叉树的后序为__B A. UWVtS B. VWUtS C. WUVtS D. WUtSV35. 某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是 dgbaechf,贝U 其后序遍历的结点访问顺序是 _DA. bdgcefhaB. gdbecfhaC. bdgaechfD. gdbehfcaB.数据之间具有分支层次关系的数据D.无太多关系的数据元素C节省存储空间 D.降低运算的时间复杂度36. 在一非空二叉树的中序遍历序列中，根结点的右边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)的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为_D _____A. 23B. 37C.46D. 4340. 利用二叉链表存储树，则根结点的右指针是_C ______A.指向最左孩子B.指向最右孩子C.空D.非空41. 下列存储方式中，哪一个不是树的存储形式？ D .A.双亲表示法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)},则对该图进行深度优先遍历,得到的序列为: ______________ D_ A. abecdf B. acfebd C. aebcfd D. aedfcb46. 下述几种排序方法中，要求内存量最大的是_D_。

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

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