发布时间 : 星期五 文章专升本数据结构5年真题和详细解析更新完毕开始阅读f84d4f54b52acfc789ebc9da
第二步：由以上判断可知，如果记录中存在82，则一定在R[7]之后（因为R是非递减有序的）。故修改low和high如下：
high值不变，仍然有high＝13；
low的值修改：使其指向R[7]的后一个元素，即使low＝mid+1 ＝ 8 ; 比较范围缩小至R[8]～R[13]。
元素下标 1 2 3 4 5 6 7 8 9 10 11 12 13 元素关键字 1 3 9 12 32 41 45 62 75 77 82 95 100 low=8 mid=10 high=13
mid ＝ ?(low +high)/2? = 10 则有R[mid]＝R[10]＝77<82
第三步：由以上判断可知，如果记录中存在82，则一定在R[10]之后（同样因为R是非递减有序的）。故修改low和high的值如下：
元素下标 1 2 3 4 5 6 7 8 9 10 11 12 13 元素关键字 1 3 9 12 32 41 45 62 75 77 82 95 100 low=11 mid=12 high=13
low的值修改，使其指向R[10]的下一个元素，即low＝mid＋1＝11; high不变，仍然是13。
mid ＝ ?(low +high)/2? =12 则有R[mid]＝R[12]＝95。
第四步：由以上判断可知，如果记录中存在82，则一定在R[12]之前（同样因为R是非递减有序的）。故修改low和high的值如下：
元素下标 1 2 3 4 5 6 7 8 9 10 11 12 13 元素关键字 1 3 9 12 32 41 45 62 75 77 82 95 100 low=11 mid=11 high=11
high的值修改，使其指向R[12]的前一个元素，即high＝mid-1＝11; low不变，仍然是11。
mid ＝ ?(low +high)/2? =11 则有R[mid]＝R[11]＝82。查找成功。 三、【答案】 （1）构造过程如下：
46 46 46 46 46 57 57 32 57 32 57 84 84 73 84 46 32 46 46 32 57 15 57 32 57 36 73 84 36 73 84 15 36 48 73 84 46 46 32 32 57 15 15 36 48 73 84 73 20 90 90 36 48 84 57
（2）平均查找长度为：（1+2*2+3*4+4*3）/10=2.9 四、【答案】
已知指向这个结点的指针是p，那么要删除这个结点的直接前趋结点，就只要找到一个结点，它的指针域是指向p的直接前趋，然后用后删结点法，将结点p的直接前趋结点删除即可。 算法如下：
void DeleteNode( ListNode *p)
{//删除单循环链表中指定结点的直接前趋结点 ListNode *s, *q; s=p;
while( s->next->next!=p) s=s->next; //删除结点 q=s->next; s->next=q->next; free(s); //释放空间 }
注意：若单循环链表的长度等于1，则只要把表删空即可。 五、【答案】
算术表达式中各种括号的使用规则为：出现左括号，必有相应的右括号与之匹配，并且每对括号之间可以嵌套，但不能出现交叉情况。我们可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配情况。在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论。
（1）当遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号；
（2）从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况； （3）算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。 下面是解决这个问题的完整算法。 typedef char StackEntry; int Check( ) {
STACK S; //定义栈结构S char ch;
InitStack(&S); //初始化栈S
while ((ch=getchar())!=?\\n?) { //以字符序列的形式输入表达式 switch (ch) {
case (ch==?(?||ch== ?[?||ch== ?{?): Push(&S,ch);break; //遇左括号入栈 //在遇到右括号时，分别检测匹配情况
case (ch== ?)?): if (StackEmpty(S)) retrun FALSE; else {Pop(&S,&ch);
if (ch!= ?(?) return FALSE; } break;
case (ch== ?]?): if (StackEmpty(S)) retrun FALSE; else {Pop(&S,&ch);
if (ch!= ?[?) return FALSE; } break;
case (ch== ?}?): if (StackEmpty(S)) retrun FALSE; else {Pop(&S,&ch);
if (ch!= ?{?) return FALSE; } break; default:break; } }
if (StackEmpty(S)) return TRUE; else return FALSE; }
2008年山东省专升本考试数据结构真题
一、单项选择题（10分、每题1分）
1、在一个单链表，已知p所指向的是q所指向结点的前驱结点，若在q和p之间插入s所指向的结点，则执行（ ）
A、s->next=q->next;q->next=s B、q->next=s->next;s->next=q C、p->next=s;s->next=q D、q->next=s;s->next=p 2、串是（ ）
A、一些符号构成的序列 B、一些字母构成的序列
C、一个以上的字符构成的序列 D、任意有限个字符构成的序列
3、数组A[10][10]的下标下界为1，每个元素占2个字节，存储在起始地址为100的连续内存单元，则元素A[3][8]的地址为（ ）
A、138 B、154 C、111 D、145
4、已知广义表L=((x,y,z),a,(u,t,w)),则从L中取出原子项y的操作是（ ） A、head(tail(head(L))) B、head(head(tail(tail(tail(L))))) C、head(tail(tail(tail(tail(L))))) D、head(tail(tail(head(tail(L)))))
5、已知完全二叉树有80个结点，则整个二叉树有____个度为2的结点。（ ） A、39 B、41 C、40 D、38 6、赫夫曼树中度为1的结点个数为（ ） A、0 B、1 C、2 D、不确定
7、具有n个顶点的有向完全图，边的总数为（ ） A、n B、n(n-1) C、n-1 D、n(n-1)/2
8、二分查找法适用于存储结构为____的，且按关键字排好序的线性表。（ ） A、顺序存储 B、链接存储 C、顺序存储或链接存储 D、索引存储
9、下列排序算法中，第一趟排序结束后，其最大或最小元素一定在其最终位置上的算法是（ ）
A、归并排序 B、直接插入排序 C、快速排序 D、起泡排序 10、一个有向无环图的拓扑序列个数是（ ）
A、1个 B、1个或多个 C、0个 D、多个 二、正误判断题（10分，正确打√，错误打×，每小题1分）
1、链表中结点数据域占的存储空间越多，存储密度越小。（ ）
2、带头结点和不带头结点的单链表在查找、删除、求长度等操作上无区别。（ ） 3、如果两个串串长相等且对应字符也相同，则这两个串相等。（ ） 4、压缩存储的三角矩阵和对称矩阵的存储空间不相同。（ ） 5、满二叉树是完全二叉树。（ ）
6、对于给定的树，与其对应的二叉树是唯一的。（ ）
7、线索二叉树的指针域中，指向前驱或后继的个数少于指向孩子的个数。（ ） 8、给定图的邻接矩阵存储不一定唯一。（ ）
9、若一个有向图的邻接矩阵主对角线以下的元素均为0，则该图拓扑有序序列存在。（ ）
10、对n个记录进行直接插入排序，其平均时间复杂度为O(nlog2n）。（ ） 三、填空题（10分，1题每空2分，其他题每空1分）
1、下列函数的功能是实现带头结点的单链表逆置。