模拟题(通信)

一：选择题（每题1分，共30分） 1：串是一种特殊的线性表，其特殊性表现在（ ）。 （A）可以顺序存储 （B）数据元素是一个字符 （C）可以连接存储 （D）数据元素可以是多个字符 2：设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B之间插入结点X的操作序列为（ ）。 （A）q->next=s； s->next=p （B）p->next=s； s->next=q （C）s->next=p->next； p->next=s （D）p->next=s->next； s->next=p 3：在一个以h为头的单循环链表中，p指针指向链尾的条件是（ ）。 （A）p->next=h （B）p->next=null （C）p->next->next=h （D）p->data=-1 4：在序列表｛2，5，7，10，14，15，18，23，35，41，52｝中，用二分法查找关键码12需做（ ）次关键码比较。 （A）5 （B）4 （C）3 （D）2 5：在有n个结点的二叉链表中，值为非空的链域个数为（ ）。 （A）2n-1 （B）n-1 （C）n+1 （D）2n+1 6：用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的出度为（ ）。 （A）第i列非0元素的个数之和 （B）第i行非0元素的个数之和 （C）第i行0元素的个数之和 （D）第i列0元素的个数之和 7：一组记录为｛46，79，56，38，84，40｝，则采用选择排序法按升序排列时第一趟排序结果是（ ）。 （A）46，79，56，38，40，84 （B）38，79，56，46，84，40 （C）38，40，46，56，84，79 （D）46，56，38，79，40，84 8：用顺序法查找一个长度为10的线性表，查找不成功时，需比较（ ）次。 （A）0 （B）10 （C）4 （D）1 „„ 二：判断题（正确的请打“√”，错误的请打“×”，每题1分，共10分） 1：《数据结构》是一门研究非数值计算的程序设计问题中计算机的操作对象以及 第 １ 页 共 3 页

算法与数据结构 模拟题 它们之间关系和操作的学科。 （ ） 2：线性表中，除第一个元素外，其他每一个元素有且仅有一个直接前驱；除最 后一个元素外，其他每一个元素有且仅有一个直接后继。 （ ） 3：对矩阵进行压缩存储主要是是为了操作方便。 （ ） 4：图的邻接矩阵是一种顺序分配和链式分配相结合的存储方法。 （ ） „„ 三：综合题（每题5分，共30分） 1：写出下列稀疏矩阵的转置矩阵的三元组顺序表（三元组以行序为主序排列）。 ．．．． 0 1 0 0 -1 i j v 4 0 0 0 0 A= 0 0 0 7 0 0 6 0 0 0 8 0 9 0 0 0 0 0 0 0 2：下表是某计算机专业前4个学期的相关课程及其先修课程状况，利用所学知识根据表中内容排出课程表，要求每门课程都不能与其先修课程在同一学期开设。 课程代码 C1 C2 C3 C4 C5 C6 C7 C8 C9 课程名称 高等数学 程序设计基础 离散数学 数据结构 高级语言程序设计 编译方法 操作系统 普通物理 计算机原理 先修课程 C1， C2 C3， C2 C2 C5， C4 C4， C9 C1 C8 3：用普里姆算法求下面带权无向图的最小生成树。 第 ２ 页 共 3 页

算法与数据结构 模拟题 4：某次考试某门课程学生成绩经过统计后，其分布规律如下表： 若要编制一个将所有百分制转换成对应的五级分制（优秀、良好、中等、及格、不及格）的程序，请用学过的知识设计最优算法，要求经过最小的比较次数后解决此问题。 四：算法设计题（共30分） 1：某线性表包含数据：（10，20，30，40，50，60，70，80，90，100），要求： 1）设计算法建立单链表存储数据； 2）设计算法确定单链表长度； 3）设计算法查找链表中是否有值为x的元素； 4）设计算法在第i个元素之后插入值为e的元素。 5）设计算法删除链表中d 第i个元素。 2：设计算法实现求稀疏矩阵M的转置矩阵T. 1）采用二维数组存储矩阵。 2）采用三元组顺序表存储矩阵非零元素。 3：写出简单模式匹配算法StrIndex。 4：设计算法求得某二叉树T（指向根结点的指针）中结点的总个数、 结点个数 以及二叉树的深度。 5：写出折半查找算法BinarySearch，返回x在有序表L（升序排序）中的位序。 6：写出简单选择排序算法SelectSort，实现待排序表L按关键字的由小到大排序。

第 ３ 页 共 3 页