《河北工业大学廊坊分校_2011_届__数据结构试卷及答案20》由会员分享，可在线阅读，更多相关《河北工业大学廊坊分校_2011_届__数据结构试卷及答案20（20页珍藏版）》请在金锄头文库上搜索。
1、数据结构数据结构试卷及答案试卷及答案1算法分析的目的是( C )。A.找出数据结构的合理性 B.研究算法中输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性2 （ B ）是具有相同特性数据元素的集合，是数据的子集。A.数据符号 B.数据对象 C.数据 D.数据结构3用链表表示线性表的优点是 ( C )。A.便于随机存取 B.花费的存储空间比顺序表少 C.便于插入与删除 D.数据元素的物理顺序与逻辑顺序相同4输入序列为（A,B,C,D）不可能的输出有（ D ） 。A.(A,B,C,D) B. (D,C,B,A) C. (A,C,D,B) D . (C,A,B,D)5在数组
2、表示的循环队列中，front、rear 分别为队列的头、尾指针，maxSize为数组的最大长度，队满的条件是( B )。A. front=maxSize B. (rear+1)%maxSize=front C. rear=maxSize D. rear=front6设有串 t=I am a good student ，那么 Substr(t,6,6)=（ D ） 。A. student B. a good s C. good D. a good7设有一个对称矩阵 A，采用压缩存储方式，以行序为主序存储 a11 为第一个元素，其存储地址为 1，每个元素占一个地址空间，则 a85 地址为（ B ）
3、 。A.23 B.33 C.18 D. 408已知广义表 LS=(A,(B,C,D),E)运用 head 和 tail 函数，取出 LS 中原子 B 的运算（C ） 。A. Gethead(Gethead(LS) B. Gettail(Gethead(LS) C. Gethead(Gethead(Gettail(LS) D. Gethead(Gettail(LS)9若已知一棵二叉树先序序列为 ABCDEFG，中序序列为 CBDAEGF，则其后序序列为( A ) 。A. CDBGFEA B. CDBFGEA C. CDBAGFE D. BCDAGFE10下列存储形式中，(C ) 不是树的存储形式
4、。A.双亲表示法 B.左子女右兄弟表示法 C.广义表表示法 D.顺序表示法11对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是 (C )。A.直接选择排序 B.直接插入排序 C.快速排序 D.起泡排序12采用折半查找方法进行查找，数据文件应为（ A） ，且限于（ ） 。A.有序表 顺序存储结构 B.有序表 链式存储结构 C.随机表 顺序存储结构 D.随机表 链式存储结构13就平均查找速度而言，下列几种查找速度从慢至快的关系是（ B ）A.顺序 折半 哈希 分块 B.顺序 分块 折半 哈希 C.分块 折半
5、哈希 顺序 D.顺序 哈希 分块 折半14执行下面程序段时，执行 S 语句的次数为（D ）for(int I=1;Idata);if(p-rchild!=NULL) (3) ; stacktop=p-rchild;if( (4) ) top+; (5) ; （1）T(2) top0(3) top+(4) p-lchild!=NULL(5) stacktop=p-lchild3.请在标号处填写合适的语句。完成下列程序。(每空 1 分，共 5 分)int Binary_Search(S_TBL tbl，KEY kx) /* 在表tbl 中查找关键码为kx的数据元素，若找到返回该元素在表中的位置，否
6、则，返回0 */int mid，flag=0；low=1；high=length； while( （1）lowAj(3) minval=Aj(4) i!=j(5) Ai+1=Aminidx5 试写出求有向无环图的关键路径算法的设计思路（10 分）输入顶点和弧信息，建立其邻接表计算每个顶点的入度对其进行拓扑排序排序过程中求顶点的 Vei将得到的拓扑序列进栈按逆拓扑序列求顶点的 Vli计算每条弧的 ei和 li,找出 ei=li的关键活动数据结构试卷 A 答案选择题（本大题共 20 小题，每题 1 分，共 20 分；答案填在下表内）12345678910C B: C: D: B: D: B: C:
7、 A: C11121314151617181920: CA: B: D: B: A: C: ACD二、填空题（本大题共 5 小题，每空 1 分，共 12 分；答案填在下表内）1有穷性 确定性 可行性2可读性 健壮性 效率3n(n-1)4student5队列 先进先出6(a) (a)三、判断题（对的打“” ，错的打“” 。每小题 1 分，共 10 分）1）true ; 2）flase; 3）true; 4）true; 5）flase;6）flase ; 7）true; 8）true; 9）flase; 10）true四、画出树的孩子兄弟表示法示意的树或森林。 （4 分）ABCDEFGHI其他形式
8、的树形结构酌情给分。五、要求题（本大题共 2 小题，共 12 分）1.4574574572142571256143324517324517632461752.一趟划分后的数据序列 3 1 2 4 7 5 6六、按要求做题（六、按要求做题（1212 分）分）1 1 DFS 遍历序列 v1 v2 v4 v8 v5 v3 v6 v7(或 1 2 4 8 5 3 6 7) BFS 遍历序列 v1 v2 v3 v4 v5 v6 v7 v8(或 1 2 3 4 5 6 7 8)邻接点的顺序可以不同，可以有不同的深度优先和广度优先遍历序列。 （5 分，如有错误酌情扣分。 ）2 七、算法设计题（七、算法设计题
9、（3030 分）分）1.将十进制转化成八进制数（5 分）测试用例：输入 10 输出 12 2（5 分，每空 1 分） （1）T(2) top0(3) top+(4) p-lchild!=NULL(5) stacktop=p-lchildV1V4V7V2V3V1V3V1V3V5V4V7V2V6V5V2V7V4V5V6V6V1V6V7V2V4V3V1V3V6V5V2V7V5V450405040503050 40503 （5 分，每空 1 分）（1）lowAj(3) minval=Aj(4) i!=j(5) Ai+1=Aminidx5（10 分，不同答案，酌情得分）输入顶点和弧信息，建立其邻接表计算
10、每个顶点的入度对其进行拓扑排序排序过程中求顶点的 Vei将得到的拓扑序列进栈按逆拓扑序列求顶点的 Vli计算每条弧的 ei和 li,找出 ei=li的关键活动第 2 学期 数据结构试卷 A一、选择题（本大题共 15 小题，每题 2 分，共 30 分；答案填在下表内）1.从一个长度为 100 的顺序表中删除第 30 个元素时需向前移动 A 个元素A、70 B、71 C、69 D、302.在一个具有 N 个单元的顺序表中,假定以地址低端(即下标为 1 的单元)作为底,以top 作为顶指针,则当做进栈处理时 top 变化为_D_。A、 top 不变 B、top=0 C、top=top-1 D、top
11、=top+13.从一个具有 n 个结点的单链表中查找其值等于 x 结点时,在查找成功情况下,则平均比较_D_个结点。A、n B、n/2 C、(n-1)/2 D、(n+1)/24.在一个单链表中,若要删除 p 指针所指结点的后继结点,则执行 BA、p- next; p- next=p- next- next;B、p- next=p- next- next;C、p=p- next;D、p=p- next-next;5.在一个链队列中,假定 front 和 rear 分别为队首和队后指针,则进行插入 S 结点的操作时应执行_C_。A、front- next=s； front=s；B、s- next=
12、rear; rear=s；C、rear- next=s; rear=s；D、s- next=front; front=s；6.在一棵度为 3 的树中度为 3 的结点数为 3 个,度为 2 的结点数为 1 个,度为 1的结点数为 1 个,那么度为 0 的结点数为_C_个A、6 B、7 C、 8 D、97.假定一棵二叉树的结点数为 33 个,则它的最小高度为_,最大高度为_C_A、 4,33 B、5,33 C、6,33 D、6,328. 在一棵完全二叉树中,若编号为 i 的结点有右孩子,则该结点的右孩子编号为_B_。A、2i B、2i+1 C、2i-1 D、i/29.在一个有向图中,所有顶点的入度
13、之和等于所有弧数和_A_倍。A、1 B、2 C、3 D、410.对于一个具有 N 个顶点的图,若用邻接矩阵表示,则该矩阵的大小为_D_。A、 N B、(N-1)2 C、(N+1)2 D、 N211.已知一个图如图所示，在该图的最小生成树中各边上数值之和为_B_。A、21 B、26 C、28 D、33 12.已知一个图如图所示，由该图行到的一种拓朴序列为 A A、v1 v4 v6 v2 v5 v3 B、v1 v2 v3 v4 v5 v6 C、v1 v4 v2 v3 v6 v5 D、v1 v2 v4 v6 v3 v513.二维数组 M 的元素是 4 个字符（每个字符占一个存储单元）组成的串，行下标 i 的范围从 0 到 4，列下标 j 的范围从 0 到 5，M 按行存储时元素 M24的起始地址与 M 按列存储时元素 D 的起始地址相同。A、m24 B、M42 C、M31 D、M3114.具有 6 个结点的无向图至少应有 A 条边才能保证是连通图。A、5 B、
