资源描述：
《哈工大2005春《数据结构》考试题-a》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、《数据结构》2005年春季学期考试试题（A卷）班号：姓名：班号学号姓名哈工大2005年春季学期《数据结构－A》试题考试时间120分钟满分100分题号一二三总分分数一、填空题（共20分，每两个空为1分）1．数组、栈和队列都是常见的线性表类型，数组的特点是可以在位置插入和删除元素；栈的主要特点是，即只能在插入和删除元素；队列的主要特点是，即只能在插入元素和删除元素。2．向一个长度为n的数组的第i个元素（1≤i≤n+1）之前插入一个元素时，需要向后移动个元素。若在长度为n的数组中删除第i个元素（1≤i≤n）时，需要向前移动个
2、元素。3．顺序表中逻辑上相邻的元素的物理位置相邻。单链表中逻辑上相邻的元素的物理位置相邻。在带头结点的单向链表中，除了头结点外，其他任一结点的存储位置由 指示。4．两个串相等的充分必要条件是 。空串是 ，其长度等于 ，空格串是 ，其长度等于 。5．设一棵完全二叉树具有1000个结点，则此完全二叉树有 个叶子结点，有 个度为2的结点，有个结点只有非空左子树，有 个结点只有非空右子树。设一棵深度为6的满二叉树有 个
3、内部结点和 个叶子。6．设要将序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的关键码按字母序的升序重新排列，则：冒泡排序一趟扫描的结果是 ；初始步长为4的希尔排序一趟的结果是 ；快速排序一趟扫描的结果是 。7．假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为 ；末尾元素A57的第一个字节地址为 ；若按
4、行存储时，元素A14的第一个字节地址为 ；若按列存储时，元素A47的第一个字节地址为 。8．设数组a[1…60,1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为 。设S=“A;/document/Mary.doc”，则strlen(s)= ,“/”的字符定位的位置为 。9.给出下列广义表操作的结果：（1）GetHead【((a,b),(c,d))】=== ;（2）GetHead【GetTail【((a,b),(c,d))】】=== ;（3）Get
5、Head【GetTail【GetHead【((a,b),(c,d))】】】=== ;（4）GetTail【GetHead【GetTail【((a,b),(c,d))】】】=== ;10.散列法存储的基本思想是根据 来决定 ，碰撞（冲突）指的是 ，处理碰撞的两类主要方法是 。第6页共6页《数据结构》2005年春季学期考试试题（A卷）班号：姓名：一、判断题，如果错误，请在括号中标记“×”，否则标记“√”（共15分，每题一
6、分）（ ）1.链表的每个结点中都恰好包含一个指针。链表的物理存储结构具有同链表一样的顺序。（ ）2.链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。（ ）3.线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（ ）4.顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（ ）5.线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。（ ）6.顺序存储方式只能用于存储线性结构。线性表的逻
7、辑顺序与存储顺序总是一致的。（ ）7.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n+1个非空指针域。（ ）8.二叉树中每个结点的两棵子树的高度差等于1，每个结点的两棵子树是有序的。（ ）9.二叉树中每个结点有两棵非空子树或有两棵空子树。二叉树中所有结点个数是2k-1-1，其中k是树的深度。（ ）10.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。（ ）11.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。具有12个结点的完全二叉树有5个度为2的结点。（ ）
8、12.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n-1个为空指针。（ ）13.两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈顶分别设在这片内存空间的两端。（ ）14.队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（ ）15.一个栈的
