高分——数据结构题

Question

2-2 顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下, 对有127个元素的顺序表进行插入, 平均需要移动多少个元素? 删除一个元素, 又平均需要移动多少个元素?

2-5 试设计一个实现下述要求的Locate运算的函数。设有一个带表头结点的双向链表L，每个结点有4个数据成员：指向前驱结点的指针prior、指向后继结点的指针next、存放数据的成员data和访问频度freq。所有结点的freq初始时都为0。每当在链表上进行一次Locate (L, x)操作时，令元素值为x的结点的访问频度freq加1，并将该结点前移，链接到与它的访问频度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。

如果是程序要求完整程序，如果是问答题，请给出数字答案的详细解释。谢谢

Answer 1

2.2若设顺序表中已有n个元素，又设插入火删除表中各元素的概率相等，则在插入是有n+1
个插入位置每个位置插入的概率为1/(n+1)，在删除时有n个删除位置，每个位置删除的概率为1/n
。根据上述推导，插入时平均移动127/2=63.5个元素，删除时平均移动（127-1）/2=63个元素.
2.5#include <iostream.h> //双向循环链表结点的构造函数
DblNode (Type value, DblNode<Type> *left, DblNode<Type> *right ) :
data ( value ), freq ( 0 ), lLink ( left ), rLink ( right ) { }
DblNode (Type value ) :
data ( value ), freq ( 0 ), lLink ( NULL ), rLink ( NULL ) { }

template <class Type>
DblList<Type> :: DblList ( Type uniqueVal ) {
first = new DblNode<Type>( uniqueVal );
first→rLink = first→lLink = first; //创建表头结点
current = NULL;
cout << "开始建立双向循环链表：\n";
Type value; cin >> value;
while ( value != uniqueVal ) { //每次新结点插入在表头结点后面
first→rLink = new DblNode<Type>( value, first, first→rLink );
cin >> value;
}
}

template <class Type>
void DblList<Type> :: Locate ( Type & x ) {
//定位
DblNode<Type> *p = first→rLink;
while ( p != first && p→data != x ) p = p→rLink;
if ( p != first ) { //链表中存在x
p→freq++; //该结点的访问频度加1
current = p; //从链表中摘下这个结点
current→lLink→rLink = current→rLink;
current→rLink→lLink = current→lLink;
p = current→lLink; //寻找从新插入的位置
while ( p != first && current→freq > p→freq )
p = p→lLink;
current→rLink = p→rLink; //插入在p之后
current→lLink = p;
p→rLink→lLink = current;
p→rLink = current;
}
else cout<<"Sorry. Not find!\n"; //没找到
}
照着资料打出来的

Answer 2

1
a.对第一个结点操作一致，b对空和非空表操作一致
2
线性结构，图形结构，顺序存储，链式存储
3
线性，链式
4
链式
5
n,|log2[n]|+1(|x|对x取整)
6
(log2(n+1))/2,
|i/2|,33
7
temp
=
p->next;p->next
=
p->next->next;free(temp);
8
n-1,n*(n-1)/2
9
1055
10
Bn,...B2,B1,An,...A2,A1
二
1
A
2
C
3
B
4
C
5
C
三
1
F
2
F
3
T
4
F
5
T
6
F
7
F
8
T
9
T
10
F