2004年下半年全国自考数据结构真题及答案.doc

更多优质自考资料尽在百度贴吧自考乐园俱乐部 （/club/5346389）欢迎?加入...欢迎?交流...止不住的惊喜等着你......... 2004年下半年全国自考数据结构真题 一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项 中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均 无分。 1. A. A B. B C. C D. D 答案：D 2. 若要在单链表中的结点*p之后插入一个结点*s，则应执行的语句是（） A. s-next=p-next;p-next=s; B. p-next=s;s-next=p-next; C. p-next=s-next;s-next=p; D. s-next=p;p-next=s-next; 答案：A 3. 若要在O（1）的时间复杂度上实现两个循环链表头尾相接，则应对两个循环链表各设置一 个指针，分别指向（） A. 各自的头结点 B. 各自的尾结点 C. 各自的第一个元素结点 D. 一个表的头结点，另一个表的尾结点 答案：B 4. 栈的两种常用存储结构分别为（） A. 顺序存储结构和链式存储结构 B. 顺序存储结构和散列存储结构 C. 链式存储结构和索引存储结构 D. 链式存储结构和散列存储结构 答案：A 5. 已知循环队列的存储空间为数组data［21］，且当前队列的头指针和尾指针的值分别为8和 3，则该队列的当前长度为（） A. 5 B. 6 C. 16 D. 17 答案：C  6. 已知在如下定义的链串结点中，每个字符占1个字节，指针占4个字节，则该链串的存储密 度为typedef struct node { char data［8］; struct node *next; } LinkStrNode;（） A. 1/4 B. 1/2 C. 2/3 D. 3/4 答案：C 7. 应用简单的匹配算法对主串s=″BDBABDABDAB″与子串t=″BDA″进行模式匹配，在匹配成 功时，进行的字符比较总次数为（） A. 7 B. 9 C. 10 D. 12 答案：C 8. 二维数组A［20］［10］采用列优先的存储方法，若每个元素占2个存储单元，且第1个元素 的首地址为200，则元素A［8］［9］的存储地址为（） A. 574 B. 576 C. 578 D. 580 答案：B 9. 对广义表L=((a,b),c,d)进行操作tail(head(L))的结果是（） A. （c,d） B. (d) C. b D. (b) 答案：D 10. 已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列 为（） A. ABCDEF B. ABCEFD C. ABFCDE D. ABCDFE 答案：D  11. 一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶 点出度的时间复杂度为（） A. A B. B C. C D. D 答案：A 12. 在关键字序列(12，23，34，45，56，67，78，89，91)中二分查找关键字为45、89和12的 结点时，所需进行的比较次数分别为（） A. 4，4，3 B. 4，3，3 C. 3，4，4 D. 3，3，4 答案：B 13. 下列排序方法中，最好与最坏时间复杂度不相同的排序方法是（） A. 冒泡排序 B. 直接选择排序 C. 堆排序 D. 归并排序 答案：A 14. 已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成 功的平均查找长度等于（） A. 1.0 B. 2.9 C. 3.4 D. 5.5 答案：B 15. 在下列各种文件中，不能进行顺序查找的文件是（） A. 顺序文件 B. 索引文件 C. 散列文件 D. 多重表文件 答案：C  二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填上正确答 案。错填、不填均无分。 1. 抽象数据类型是指数据逻辑结构及与之相关的___。 答案：操作 2. 已知在结点个数大于1的单循环链表中，指针p指向表中某个结点，则下列程序段执行结束 时，指针q指向结点*p的___结点。 q=p; while (q-next!=p) q=q-next; 答案：前驱 3. 假设S和X分别表示进栈和出栈操作，由输入序列“ABC”得到输出序列“BCA”的操作序列 为SSXSXX，则由“a*b+c/d”得到“ab*cd/+”的操作序列为___。 答案：SXSSXXSSXSSXXX 4. 在文本编辑程序中查找某一特定单词在文本中出现的位置，可以利用串的___运算。 答案：子串定位（或模式匹配） 5. 假设以行优先顺序将一个n阶的5对角矩阵压缩存储到一维数组Q中