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