数据结构A卷教程.doc

第  PAGE 9 页 共  NUMPAGES 9 页 院/系 年级 专业 姓名 学号 答 题 勿 超 装 订 线 装订线   安徽大学20 09 —20 10学年第 2 学期 《 数据结构 》考试试卷（A卷） （闭卷 时间120分钟） 题 号一二三四五六七总分得 分阅卷人 得分 一、填空题（每空1分，共15分） 1、在线性结构中，第一个结点 前驱结点，其余每个结点有且只有 个前驱结点；最后一个结点 后续结点，其余每个结点有且只有 个后续结点。 2、下面程序段的时间复杂度是 。 for (i=0;in;i++) for (j=0;jm;j++) A[i][j]=0; 3、在具有n个单元的循环队列中，队满时共有 个元素。 4、假定一棵二叉树的结点数为18，则它的最小深度为 ，最大深度为 。 5、在一个单链表中p所指结点之后插入一个s所指结点时，应执行下面的操作： s—＞next=_ ___; p—＞next=___; 6、从有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素时，其查找长度分别为 和 。 7、.一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结点有___________________个。 8、在堆排序和快速排序中，若原始记录接近正序或反序，则选用____。 9、若采用邻接表的存储结构，则图的广度优先搜索类似于二叉树的________遍历。 得分 二、单向选择题（每小题1.5分，共15分） 1、n个顶点的强连通图中至少含有( )。 A、n—l条有向边 B、n条有向边 C、n(n—1)／2条有向边 D、n(n一1)条有向边 2、在一个不带头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，执行( )。 A、 HL＝p; p一next＝HL; B、 p一next＝HL；HL＝p; C、 p一next＝HL; p＝HL; D、 p一next＝HL一next; HL一next＝p; 3、采用线性链表表示一个向量时，要求占用的存储空间地址（ ）。 A: 必须是连续的 B 部分地址必须是连续的 C: 一定是不连续的 D: 可连续可不连续 4、如果想在4092个数据中只需要选择其中最小的5个，采用（ ）方法最好。 A: 起泡排序 B: 堆排序 C: 锦标赛排序 D: 快速排序 5、在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（ ）。 A: ( front - rear + 1) % m B: ( rear - front + 1) % m C: ( front - rear + m) % m D: ( rear - front + m) % m 6、数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是(????? )。 A: 1175??????????? B: 1180??????????? C: 1205??????????? D: 1210 7、已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是(???? ) A: head(tail(LS))????????????????????? B: tail(head(LS))C: head(tail(head(tail(LS)))?????????? D: head(tail(tail(head(LS)))) 8、某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是（ ）。 A: bdgcefha B: gdbecfha C: bdgaechf D: gdbehfca 9、在一个无向图中,所有顶点的度数之和等