全国2003年10月高等教育自学考试数据结构试题

个人采集整理-ZQ.计算机辨别、储存和加工办理地对象被统称为().数据.数据元素.数据构造.数据种类.在拥有个结点地有序单链表中插入一个新结点并使链表仍旧有序地时间复杂度是()()()()().队和栈地主要差别是().逻辑构造不一样.储存构造不一样.所包括地运算个数不一样.限制插入和删除地地点不一样.链栈与次序栈对比，比较显然地长处是().插入操作更为方便.删除操作更为方便.不会出现下溢地状况.不会出现上溢地状况.采纳两类不一样储存构造地字符串可分别简称为().主串和子串.次序串和链串.目标串和模式串.变量串和常量串.在目标串［］″″中，对模式串［］″″进行子串定位操作地结果是()文档采集自网络，仅用于个人学习.已知广义表地表头为，表尾为()，则此广义表为().(,()).().(()).(()).二维数组按行优先次序储存，此中每个元素占个储存单元.若［］［］地储存地点为，［］［］地储存地点为，则［］［］地储存地点为()文档采集自网络，仅用于个人学习.二叉树中第层上地结点个数最多为().以下编码中属前缀码地是().{}.{}文档采集自网络，仅用于个人学习.{}.{}文档采集自网络，仅用于个人学习.假如某图地毗邻矩阵是对角线元素均为零地上三角矩阵，则此图是().有向完好图.连通图.强连通图.有向无环图.对个重点字地序列进行迅速排序，均匀状况下地空间复杂度为()()()()().对表长为地次序表进行次序查找，在查找概率相等地状况下，查找成功地均匀查找长度为()文档采集自网络，仅用于个人学习....关于哈希函数(),被称为同义词地重点字是()和和1/5个人采集整理-ZQ和和.浓密索引是在索引表中().为每个记录成立一个索引项.为每个页块成立一个索引项.为每组记录成立一个索引项.为每个字段成立一个索引项二、填空题（每题分，如有两个空格，每个空格分，共分）.当问题地规模趋势无量大时，算法履行时间()地数目级被称为算法地(时间复杂度).文档采集自网络，仅用于个人学习.在链表地结点中，数据元素所占地储存量和整个结点所占地储存量之比称作(储存密度).文档采集自网络，仅用于个人学习.已知链栈地结点构造为栈顶指针为，则实现将指针所指结点插入栈顶地语句挨次为和.文档采集自网络，仅用于个人学习.空串地长度是；空格串地长度是(空格地数目)..假定一个阶地下三角矩阵按列优先次序压缩储存在一维数组中，此中［］储存矩阵地第一个元素,则［］储存地元素是.文档采集自网络，仅用于个人学习.在一棵度为地树中，度为地结点个数是，度为地结点个数是，则度为地结点个数是.文档收集自网络，仅用于个人学习.如下图地有向无环图能够排出种不一样地拓扑序列..利用挑选法将重点字序列(，，，，，)建成地大根堆为().文档采集自网络，仅用于个人学习.对长度为地有序表进行二分查找地判断树地高度为..在多重表文件中，次重点字索引地组织方式是将地记录链接成一个链表..关于单链表、单循环链表和双向链表，假如只是知道一个指向链表中某结点地指针，可否将所指结点地数据元素与其的确存在地直接前驱互换?请对每一种链表作出判断，若能够，写出程序段；不然说明原因.文档采集自网络，仅用于个人学习单链表和单循环链表地结点构造为双向链表地结点构造为()单链表:(不能够,没法找到前驱接点)()单循环链表(能够>(>)>><>>;文档采集自网络，仅用于个人学习()双向链表(能够>><>>;).假定通讯电文使用地字符集为{}，字符地哈夫曼编码挨次为：，，，，，和.文档采集自网络，仅用于个人学习()请依据哈夫曼编码画出此哈夫曼树，并在叶子结点中标明相应字符；()若这些字符在电文中出现地频度分别为：，，，，，和，求该哈夫曼树地带权路径长度.文档采集自网络，仅用于个人学习.当采纳毗邻表作为图地储存构造时，也可将毗邻表中地极点表由次序构造改为链表构造.()请分别画出这类毗邻表地极点链表结点和边表结点，并说明结点中各个域地作用；()对如下图地有向图画出这类毗邻表..已知阶树如下图.()分别画出将重点字和接踵插入以后地树.()画出从插入以前地树中删除重点字以后地树.四、算法阅读题(每题分，共分).阅读以下函数,并回答以下问题：2/5个人采集整理-ZQ()假定行列中地元素为(),此中“”为队头元素.写出履行函数调用()后地行列；文档采集自网络，仅用于个人学习()简述算法地功能.(*){;();(())(,());(!())(());}()()行列倒置.阅读以下函数，并回答以下问题：()已知如下图地二叉树以二叉链表作储存构造，为指向根结点地指针.写出履行函数调用()地输出结果.文档采集自网络，仅用于个人学习()说明函数地功能.(){;(){();();(){("",>);(>);(>)>;();}}}()()前序遍历二叉数.已知毗邻表地极点表结点构造为边表结点地构造为以下算法计算有向图中极点地入度.请在空缺处填入适合地内容，使其成为一个完好地算法.(*)为图地毗邻表种类{,;3/5个人采集整理-ZQ*;();(<>){>［］.;(()){(()){;;}>;}};}();()()>.已知单链表地结点构造为以下算法对带头结点地单链表进行简单项选择择排序，使得中地元素按值从小到大摆列.请在空缺处填入适合地内容，使其成为完好地算法.(){;;();(){;>;(){(());>;}(()){>;>>;>;}();}}4/5个人采集整理-ZQ()>()><>()()>五、算法设计题(此题分).设线性表(,)以带头结点地单链表作为储存构造.编写一个函数，对进行调整，使适当为奇数时(,,)，当为偶数时(,,).文档采集自网络，仅用于个人学习{;*;};*;(){*;用来保留偶数链表尾指针>;链表遍历指针>奇数链表头指针>奇数链表尾指针奇数结点标记，第一个结点是奇数结点()空链表，不需要办理;(>)从第