《数据结构》试题（100分）（供2005级信息管理与信息系统本科专业使用）学号： 姓名： 座号： 系别： 年级： 专业：总分合计人： 复核人：说明：本试卷分为两部分，第I 卷（选择题和判断题）必须在“答题卡”上按规定要求填、涂；第II 卷直接在试卷上作答。
不按规定答题、填涂，一律无效。
第I 卷一、试题类型：单项选择题（每小题2分，共40分） （类型说明：在每小题列出的四个选项中只有一个选项是符合题目要求的，请选出正确选项并在“答题卡”的相应位置上涂黑。
多涂、少涂、错误均无分。
）1. 算法分析的两个主要方面是：（ ）（A) 空间复杂性和时间复杂性 （B) 正确性和简明性 （C) 可读性和文档性 （D) 数据复杂性和程序复杂性2. 计算机算法指的是： （ ）（A) 计算方法 （B) 排序方法 （C) 解决问题的有限运算序列 （D) 调度方法 3． 数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称为：（ ）（A ）存储结构 （B ）逻辑结构 （C ）顺序存储结构 （D ）链式存储结构 4.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是 。
（ ）（A ）110 （B ）108 （C ）100 （D ）1205. 链接存储的存储结构所占存储空间： （ ）（A ）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 （B ）只有一部分，存放结点值（C ） 只有一部分，存储表示结点间关系的指针（D ） 分两部分，一部分存放结点值，另一部分存放结点所占单元数 6. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址: （ ）（A ）必须是连续的 （B ）部分地址必须是连续的 （C ）一定是不连续的 （D ）连续或不连续都可以7. 栈中元素的进出原则是：（）（Ａ）先进先出（Ｂ）后进先出（Ｃ）栈空则进（Ｄ）栈满则出8. 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为：（）（Ａ） i （Ｂ） n=i （Ｃ） n-i+1 （Ｄ）不确定9. 串是一种特殊的线性表，其特殊性体现在：（）（Ａ）可以顺序存储（Ｂ）数据元素是一个字符（Ｃ）可以链式存储（Ｄ）数据元素可以是多个字符10. 设串s1=‘ABCDEFG’，s2=‘PQRST’，函数con(x,y)返回x和y串的连接串，subs(s, i, j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2))的结果串是：（）（Ａ）BCDEF （Ｂ）BCDEFG （Ｃ）BCPQRST （Ｄ）BCDEFEF11. 假设有60行70列的二维数组a[1…60, 1…70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为。
（无第0行第0列元素）（）（Ａ）16902 （Ｂ）16904 （Ｃ）14454 （Ｄ）答案A, B, C均不对12．二叉树是非线性数据结构，所以。
（）（Ａ）它不能用顺序存储结构存储; （Ｂ）它不能用链式存储结构存储;（Ｃ）顺序存储结构和链式存储结构都能存储;（Ｄ）顺序存储结构和链式存储结构都不能使用13. 具有n(n>0)个结点的完全二叉树的深度为。
（）(Ａ) ⎡log2(n)⎤ (Ｂ) ⎣ log2(n)⎦ (Ｃ) ⎣ log2(n) ⎦+1 (Ｄ) ⎡log2(n)+1⎤14．把一棵树转换为二叉树后，这棵二叉树的形态是。
（）（Ａ）唯一的（Ｂ）有多种（Ｃ）有多种，但根结点都没有左孩子（Ｄ）有多种，但根结点都没有右孩子15. 已知图的邻接表如下所示，则从顶点0出发按深度优先遍历的结点序列是（）16.已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是（）17．折半查找有序表（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）0 1 3 2 （B） 2 0 3 1（C） 1 3 2 0 （D）0 1 2 3（A）0 3 2 1 （B） 1 2 3 0（C）3 2 1 0 （D） 3 0 1 218．链表是一种采用存储结构存储的线性表。
（）（A）顺序（B）链式（C）星式（D）网状19．不含任何结点的空树。
（）（Ａ）不是一棵树; （Ｂ）不是一棵二叉树;（Ｃ）是一棵树也是一棵二叉树; （Ｄ）既不是树也不是二叉树20．在一个图中，所有顶点的度数之和等于图的边数的倍。
（）A．1/2 B. 1 C. 2 D. 4二、试题类型：判断题（每小题1分，共10分）（类型说明：判断正确答案，选项并在“答题卡”的相应位置填涂，认为正确的涂“A”错误的涂“B ”。
多涂、少涂、错误均无分。
）21. 二叉树中每个结点的两棵子树是有序的。
（）22. 顺序存储方式只能用于存储线性结构。
（）23. 二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。
（）24. 栈和队列的存储方式既可是顺序方式，也可是链接方式。
（）25. 二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。
（）26. 队列是一种先进后出型结构。
（）27. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。
（）28. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。
（）29. 线性表在物理存储空间中也一定是连续的。
（）30. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。
（）第II卷三、试题类型：填空题（每空1分，共10分）（类型说明：请将正确答案填于试题预留的横线上。
）31. 栈是一种特殊的线性表，允许插入和删除运算的一端称为。
不允许插入和删除运算的一端称为。
32. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动个元素。
33. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动个元素。
34. 假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。
已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为；末尾元素A57的第一个字节地址为；若按行存储时，元素A14的第一个字节地址为；若按列存储时，元素A47的第一个字节地址为。
35. 设S=“A;/document/Mary.doc”，则strlen(s)= , “/”的字符定位的位置为。
四、试题类型：简答题（每小题5分，共30分）（类型说明：）36. 已知二维数组Am,m采用按行优先顺序存放，每个元素占K个存储单元，并且第一个元素的存储地址为Loc(a11)，请写出求Loc(aij)的计算公式。
37. 用三元组表表示下列稀疏矩阵：⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡-00000300000000050000000000000920000038. 试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。
39. 把如图所示的树转化成二叉树。
40. 已知如图所示的有向图，请给出该图的邻接表。
41. 请对下图的无向带权图，求其最小生成树；五、试题类型：分析题（每小题5分，共5分）（类型说明：）42. 已知一组关键字序列：49 38 65 97 13 27按照快速排序方法对此序列进行排序，写出每趟排序的结果。
六、试题类型：编程题（每小题5分，共5分）（类型说明：）43. 设顺序表va中的数据元素递增有序。
试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。
顺序表的存储结构如下：typedef struct {ElemType *elem; //指向存放线性表中数据元素的基地址int length; //线性表的当前长度int listsize; //当前分配的存储容量}SqList；Status InsertSqList(SqList &va,int x)//把x插入递增有序表va中{ if(va.length+1>va.listsize) return ERROR;《数据结构》A卷信管本科专业标准答案及评分标准（按试题顺序排列）一、单项选择题（每小题2分，共40分）1、A2、C3、C4、 B5、A6、D7、B8、C9、B 10、D11、A 12、C 13、C 14、A 15、D16、A 17、A 18、B 19、C 20、C二、判断题（每小题1分，共10分）21. A 22. B 23. B 24. A 25. B 26. B 27. B 28. A 29. B 30. B三、填空题（每空1分，共10分）31. 栈顶栈底32. n-i+133. n-i34. 288 B 1282 1072 127635. 20 3四、简答题（每小题5分，共30分）36. Loc(aij)= Loc(a11) +[ (i-1)*m+(j-1) ] * K37.38.先序：A B D F J G K C E H I L M---------2分中序: B F J D G K A C H E L I M----------2分后序：J F K G D B H L M I E C A----------1分39.40.41. 五、试题类型：分析题（每小题5分，共5分）42. 初始序列：49 38 65 97 13 27第一趟排序结果：27 38 13 49 97 65第二趟排序结果：13 27 38 49 65 97六、试题类型：编程题（每小题5分，共5分）43. va.length++;for(i=va.length-1;va.elem[i]>x&&i>=0;i--)va.elem[i+1]=va.elem[i];va.elem[i+1]=x;return OK; }《数据结构》试题（100分）（供2005级信息管理与信息系统本科专业使用）学号：姓名：座号：系别：年级：专业：6 6 41 6 -22 5 9 43 5 6 5 3总分合计人： 复核人：说明：本试卷分为两部分，第I 卷（选择题和判断题）必须在“答题卡”上按规定要求填、涂；第II 卷直接在试卷上作答。
不按规定答题、填涂，一律无效。
第I 卷一、试题类型：单项选择题（每小题2分，共40分）（类型说明：在每小题列出的四个选项中只有一个选项是符合题目要求的，请选出正确选项并在“答题卡”的相应位置上涂黑。