重庆理工大学算法与数据结构试卷一.pdf_第1页
重庆理工大学算法与数据结构试卷一.pdf_第2页
重庆理工大学算法与数据结构试卷一.pdf_第3页
重庆理工大学算法与数据结构试卷一.pdf_第4页
重庆理工大学算法与数据结构试卷一.pdf_第5页
已阅读5页,还剩2页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

重庆理工大学考试试卷 重庆理工大学考试试卷 一、单项选择(每题 2 分,共 20 分) 一、单项选择(每题 2 分,共 20 分) 1一个具有 n 个顶点的无向完全图的边数为( ) A.n(n+1)/2 B.n(n+1) C.n(n-1) D.n(n-1)/2 2线性表若采用链式存储结构时,要求内存中可用存储单元的地址( ) A.必须是连续的 B.部分地址必须是连续的 C.一定是不连续的 D.连续不连续都可以 3一个顺序表第一个元素的存储地址是 100,每个元素的长度为 2,则第 5 个元素 的地址是( ) A.110 B.108 C.100 D.120 4串是一种特殊的线性表,其特殊性体现在( ) A.可以顺序存储 B.数据元素是一个字符 C.可以链接存储 D.数据元素可以是多个字符 5顺序查找法适合于存储结构为( )的线性表。 A.散列存储 B.顺序存储或链接存储 C.压缩存储 D.索引存储 6下述几种排序方法中,平均时间复杂度最小的是( ) A.插入排序 B.选择排序 C.冒泡排序 D.快速排序 7. 循环队列用数组 A0, m-1存放其元素值, 已知其头尾指针分别是 front 和 rear, 则当前队列中的元素个数是 。 A. (rear-front+m) % m B. read-front+1 C. read-front-1 D. read-front 8.3 个结点可构成( )个不同形态的二叉树。 A.2 B.3 C.4 D.5 9对于关键字值序列(12,13,11,18,60,15,7,18,25,100) ,用筛选法建 堆,必须从关键字值为( )的结点开始。 A.100 B.12 C.60 D.15 10栈操作的原则是( ) A.先进先出 B.后进先出 C.栈顶插入 D.栈顶删除 二、填空题(每小题 1 分,共 10 分) ,将正确的答案写在每小题的空格内。 二、填空题(每小题 1 分,共 10 分) ,将正确的答案写在每小题的空格内。 1. 在双循环链表中,在指针 p 所指结点前插入指针 s 所指的结点,需执行下 列语句:s-next=p;s-prior=p-prior;p-prior=s; _=s; 2散列法存储中处理碰撞(冲突)的两类基本方法是 、 3. 设二维数组 A-2.10,-1.20按行优先顺序存储, 每个元素占 4 个存储单 元,A-2,-1的存储地址是 1000,则 A5,6的存储地址是 。 4. 设 s1.maxsize为一个顺序存储的栈,变量 top 指示栈顶位置,栈为空 的条件是_,栈为满的条件是_。 5 设有向图的邻接矩阵为A, 如果图中不存在弧VI, VJ, 则AIJ的值为: 。 6. 设有一个链队列,结点结构为:队尾指针为 Ls(null) ,则执行入队操 作时, S-next=Ls-next;_ _;_ _。 7. 单链表中指针P所指结点不为尾结点的条件是_ _。 8. G 为无向图,如果从 q 的某个顶点出发,进行一次广度优先搜索,即可访 问图的每个顶点,则该图一定是 图。 9. 串 S=I am a worker的长度是_ _。 10.按先根次序法遍历树林正好等同于按 遍历对应的二叉树。 、算法应用题(每小题 5 分,共 20 分) 、算法应用题(每小题 5 分,共 20 分) 到最小生成树,试在下表的空白处 顶点 1 3 4 U V 1 5 5 4 2 3 2 1 4 三三 1、 对上图所示的网,执行 prim 算法可得 填上适当的内容,以说明该算法的执行过程。 (U,V) (2,1) (2,3) (2,4) 2 1,4 代价 4 2 3, (U,V)(2,3) 2,4 1,3 代价 4 (U,V) (3,1) 2,4,3 1 代价 1 (U,V) 2,4,3,1 代价 2、有一组关键码序列8,9,1采用冒泡排、快速排序、5,3,72, ,分别序 直接选择排序、直接插入排序、二路归并排序方法由小到大进行排序,在下面 的选项中选择各种排序第一趟排序的结果。 冒泡排序: ;快速排序: ;直接选择排序: 直接插入排序: ;二路归并: A1,2,5,3,7,8,9 B1,9,5,3,7,2,8 C9,8,5,3,7,2,1 D9,5,3,7,2,1,8 E8,5,3,7,2,1,9 F8,9,3,5,2,7,1 3、设有序序列 30,18,3,61,14,49,请按该序列构成一棵二叉排序树,并求查 现有 5 个结点(A,B,C,D,E) ,它们的权值分别为5,10,12,15,30, 、算法填空和分析(每小题 5 分,共 30 分) 、算法填空和分析(每小题 5 分,共 30 分) 字符串是否是中心对称,如 ar data; next; cnode *h) ar stMaxLen; 找 3 的比较次数。 4、 在下面的选项中选择一个编号, 说明这 5 个结点的哈夫曼编码。( ) (1)A:1,B:001,C:010,D:011,E:000 (2)A:000,B:001,C:010,D:011,E:1 (3)A:001,B:011,C:010,D:000,E:1 (4)A:000,B:1,C:010,D:011,E: 001 四四 1、设单链表存放字符串,下列算法使用栈判断该 abccba 即为中心对称字符串. 根据题目填空完善程序. typedef struct node ch struct node * cnode; int judge( ch int top=0; cnode *p= ; top=p-data; while (p!=NULL) st top ; p=p-next; p= ; p while (p!=NULL) to; if (p-data sttop) p=p-next; el k; if (p= =NULL) els urn 0; void Merge (Elem SR, Elem TR, int i, int m, int n) se brea return 1; e ret 2、 / 将有序的 SRi.m和 SRm+1.n归并为有序的 TRi.n for (j=m+1, k=i; i=m +k) / 将 SR 中记录由小到大地并入 TR if (SRi.key=SRj.key) TRk =; if ( else TRk = SRj+; ) TRk.n = SRi.m;/ 将剩余的 SRi.m复制到 TR if ( ) TRk.n = SRj.n;/ 将剩余的 SRj.n复制到 TR / Merge 3、 int Partition (Elem R, int low, int high) 记录到位,并返回/其 地向中间扫描 ivotkey) -high; / 交换记录子序列 Rlow.high中的记录,使枢轴 所在位置,此时,在它之前(后)的记录均不大(小)于它 R0 = Rlow;/ 用子表的第一个记录作枢轴记录 pivotkey = Rlow.key; / 枢轴记录关键字 while (lowhigh) / 从表的两端交替 while(low=p Rlow = Rhigh;/ 将比枢轴记录小的记录移到低端 while (lownext; u=head; head=head u-next= ; head=p; 已知带权图的邻接矩阵表示和邻接表表示的形式说明分别如下: 最大整数,表示 /字符类型的顶点表 整型的邻接矩阵 p=u; 6、 #define MaxNum 50/图的最大顶点数 #define INFINITY INT_MAX /INT_MAX 为 typedef struct char vexsMaxNum; int edgesMaxNumMaxMum;/权值为 int n,e;/图中当前的顶点数和边数 MGraph;/邻接矩阵结构描述 typedef struct node int adjvex;/邻接点域 int weight;/边的权值 struct node *next;/链指针域 域 边表头指针 MaxNum;/邻接表 存储结构 G1 建立该图的邻接表存储结 i,j; p; ;i+) -adjlisti.vertex=G1-vexsi; EdgeNode;/边表结点结构描述 typedef struct char vertex;/顶点 EdgeNode * firstedge;/ VertexNode ;/顶点表结点结构描述 typedef struct VertexNode adjlist int n,e;/图中当前的顶点数和边数 ALGraph;/邻接表结构描述 下列算法是根据一个带权图的邻接矩阵 构 G2,请填入合适的内容,使其成为一个完整的算法。 void convertM(MGraph *G1,ALGraph *G2) int EdgeNode * G2-n=G1-n; G2-e=G1-e; for(i=0;in G2 G2-adjlisti.firstedge= ; =0;in;i+) +) INFINITY) (EdgeNode *) malloc(sizeof(EdgeNode); for (i for (j=0;jn;j+ if(G1-edgesijweight= ; p-adjvex=j; p-next=G2-adjlisti.firstedge; ; 编写算法(每小题 10 分,共 20 分) : 编写算法(每小题 10 分,共 20 分) : 用于存放某人的电话薄,现在由 五、五、 1、设某单链表 L 的结点结构如下,单链表 L 于电话号码从 7 位升为 8 位(加 60000000) ,请用 C 语言编写算法,实现电话 薄中所有电话号码从 7 位升为 8 位。 Typedef struct node char name9;/姓名 pointer

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论